问题:求一个正整数序列的最长单调自增子序列,子序列不要求是连续的。例如

Input:5

5 2 4 3 1

Output:2
解题思路:
(1).从a1,a2,a3,a4、…、ak-1中寻找所有比ak小的元素。
(2).找到以这些元素为重点的最长上升序列长度的最大值,将其加上1保存到当前的len[k]中。

#include<iostream>

using namespace std;

#define N 1000

int main()
{
	int a[N];
	int len[N]={0};//记录"每一个最长上升子序列"的长度
	int max;//记录最长上升子序列的长度 
	int n;
	int tempMax;
	cin>>n;
	for(int i=1;i<=n;i++)
	{//读入序列元素 
		cin>>a[i];
	}
	len[1]=1;
	for(int i=2;i<=n;i++)
	{
		tempMax=0;
		for(int k=1;k<i;k++)
		{
			if(a[k]<a[i] && tempMax<len[k])
			{
				tempMax=len[k];
			}
		}
		len[i]=tempMax+1;
	}
	max=0;
	for(int i=0;i<=n;i++)
	{
		if(len[i]>max)
		{
			max=len[i];
		}
	}
	cout<<max<<endl;	
	return 0;
}