19523 最长上升子序列长度
时间限制:1000MS 代码长度限制:10KB
题型: 编程题 语言: 不限定
Description
当元素 ai1 < ai2 <……< aiK。就说这个序列是有序上升的。
给定序列(a1, a2, ……, aN)，存在许多这样的子序列(ai1, ai2, ……, aiK)，其中1 <= i1 < i2 < ……< iK <= N。
也就是说，子序列是原序列允许挑选若干不连续的元素形成的序列。
举个例子，序列 (1, 7, 3, 5, 9, 4, 8) 就有许多个上升子序列，比如(1, 7)、(3, 4, 8) 等。
所有这些上升子序列中最长的长度为4，比如 (1, 3, 5, 8)。
你来编程实现，当给定一个初始序列，求解这个序列的最长上升子序列的长度。
输入格式
此例包含多个测试cases（少于100组test cases）。
每一组test case包含2行。
第一行是这组case的序列长度 N（N的范围0~10000）。
第二行包含 N个整数的一个序列，用空格间隔这N个整数， 1 <= N <= 10000。
当N为0时，表示测试结束。
输出格式
输出必须对每个test case，都有一个整数结果，表示这组case的最长上升子序列的长度。
输入样例
7
1 7 3 5 9 4 8
6
1 8 3 6 5 9
5
1 2 3 4 5
0
输出样例
4
4
5
问题分析：
本问题可建立一个数组，从前至后计算并保存包含该元素的最长上升子序列长度。在计算时，可在已计算的前序元素中检验，寻找能与当前元素形成递增子序列的元素中，递增子序列长度的最大值（代码中为变量m）。每次计算仅需遍历检验当前元素以前的元素一次。
代码实现：
#include<iostream>
using namespace std;
int main()
{
int n=0;
while(cin>>n&&n)
{
int ss[10005]={0};
int length[10005]={0};
int res=0;
for(int i=1;i<=n;i++)
{
cin>>ss[i];
}
for(int i=1;i<=n;i++)
{
int m=0;
for(int j=1;j<i;j++)
{
if(ss[j]<ss[i]&&length[j]>m)//能与当前数字构成上升子序列，并且已构成子序列的长度是最大的
{
m=length[j];
}
}
if(m+1>1)
length[i]=m+1;
else
length[i]=1;
if(res<length[i])
res=length[i];
}
cout<<res<<endl;
}
return 0;
}