8596最长上升子序列(优先进行) )
时间限制：300MS码长限制：10KB
提交次数：255通过次数：118
题型：编程试题语言： G； GCC； VC
描述
元素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组包含两行。
第一行是此组的case的序列长度n。 (n的范围为0~10000 )
第2行包含n个整数的1个系列，用空格隔开这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
提示
一.对输入字符串的处理
注意：此问题与其他问题的输入和输出不同。 此问题接收多组数据而不是单组，并通过0来确定结尾。
大家接收数据时，请不要使用((c=getchar ) ) )！=’ n’这样一个字符一个字符地接受，
然后判断是否是换行符号，结束一行的输入。 这样的方式在你的本机上执行也没有问题
但是，OJ系统有错误，无法输出结果。 因为测试平台的行尾没有“n”字符。
要在此接收数据，请不要在程序中，因为使用scanf的%d、%s、cin等会自动确定结束字符
来辨别和吸收返回的字符。
如果最后的数据输入为0，则判断接受的第一个字符是否为0，字符串的长度是否长即可结束
以1结尾。 不需要处理换行符。
可以用整数数组或字符串数组保存输入的序列。
二.算法的动态规划思想
研究采用动态规划算法，对各要素，将以该要素结尾的最长有序子序列作为子问题，
计算每个子问题的最大长度并用“表”记录。 写递归关系式后编程实现。
f(I )从左向右扫描，表示在以a(I )元素结尾的排列之前获得的最长上升
子序列的长度。 最长上升子序列包含a[i]元素(1=i=n )。
)在此，我们来考虑一下为什么这样假设子问题和子问题的最佳解f(I )。
一个学生问：“为什么最长上升子串中会含有a[i]元素(1=i=n )？
因为你设置的子问题必须和更低级的子问题相关联。 如果长度是I序列的最长上升
没有规定子序列包含a[i]元素，它与前缀的最长上升子序列问题有何关联
怎么样？ 因为无法确认前缀的最长上升子序列的最后一个字符在哪里。 上升子序列的
如果不知道边界在哪里，就很难和更小规模的子问题联系起来，明显很麻烦。 ) )
f(I )在f ) 1、f ) 2、……到f(I-1 )中寻找最大的值，加1或等于1。
这主要要看a[i]这一元素能否添加到以前获得的最长上升子串中
如果可以添加，则在以前获取的最长上升子序列长度上加1。
如果不能添加，则开始长度为1的新上升子序列。
最后，被要求的序列整体的最长上升部分序列长度为max{f(I ) : ) I=n}
f(I )的递归公式如下
(1) f ) I )=1当i=1；
)2)如果f(I )=max ) f ) j )1) i1，则对于某个之前的j ) j(1=ji )，a[j]a[i]；
(3)设f ) I )=1为i1，对于任意的j(1=Ji )，具有a[j]=a[i]
例如，序列：4 2 6 3 1 5 2
i=1 2 3 4 5 6 7
a[i]=4 2 6 3 1 5 2
f(I )=112132
这里max{f(I ) }=3是在原来的问题中求出的最长上升子串的长度。
效率分析：
f(I )的计算不超过o ) n )，因此整个算法为o(n^2)。
# includeiostreamusingnamespacestd； int main () {int N； int a[10001]； int n[10001]； n[0]=1； do{cinN； for(intI=0； iN； I ) {cina[i]； }for(intI=1； iN； I () n ) I )=1； for(intj=0； ji； j () if ) a[j]a[I] ) n[i]=max ) n[i]，n[i] )； }}}int maxt=-1； for(intI=0； iN； I ) ) maxt=max(maxt，n[i]； (if ) n！=0) coutmaxtendl； }while(n！=0； 返回0； }