问题:求一个正整数序列的最长单调自增子序列,子序列不要求是连续的。例如
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;
}