学步园

写一个时间复杂度尽可能低的程序，求一个一维数组N个元素中最长递增子序列的长度.

题目:
       设L=<a1,a2,…,an>是n个不同的实数的序列，L的递增子序列是这样一个子序列Lin=<aK1,ak2,…,akm>，其中k1<k2<…<km且aK1<ak2<…<akm。求最大的m值。

如：序列：1，-1，2，-3，4，-5，6，-7中最长递增子序列的长度为：1,2,4,6

方法一：

动态规划：Ｏ（Ｎ^２）

阶段间的关系具有无后效性。

阶段：在所有元素的子数组中，选出其中的最长递增子序列，k=1,2...N。
状态：以元素k结尾的最长递增子序列中只有一个最长的递增子序列。
决策：决定元素k结尾的最长递增子序列有k-1种获取的途径，前面以任何一个元素结尾的最长递增子序列都可能成为其的一部分。

#include<iostream>
using namespace std;
int LIS(int num[],int N);
int main()
{
	int N ,i;
	int *num;
	cout<<"请输入数组中元素的个数： " ;
	cin>>N;
	num=(int *)malloc(sizeof(int)*(N+1));
	cout<<"请输入" <<N<<"个元素"<<endl;
	for (i=0;i<N;i++)
	{
		cin>>num[i];
	}
	cout<<"最长子序列的长度为 ： " <<LIS(num,N)<<endl;
	return 0;
}
int LIS(int num[],int N)
{
	int X;
	int i,k;
	int *lis;
	lis=(int *)malloc(sizeof(int)*(N+1));
	//DP 阶段、 状态、决策

	for (i=0;i<N;i++)//阶段
	{
		lis[i]=1;//每个阶段只有一个状态
		for (k=0;k<i;k++)// 每个状态有i种决策,得出以元素i结尾的最长递归子序列的长度   
		{
			if (((lis[k]+1)>lis[i])&&(num[i]>num[k]))
			{
				lis[i]=lis[k]+1;
			}
		}
	}
	X=lis[0];
	for (i=1;i<N;i++)
	{
		if (X<lis[i])
		{
			X=lis[i];
		}
	}
	return X;
}