问题描述:给出一个序列a1,a2,a3,a4,a5,a6,a7....an,求它的一个子序列(设为s1,s2,...sn),使得这个子序列满足这样的性质,s1<s2<s3<...<sn并且这个子序列的长度最长。输出这个最长的长度。
O(n^2)算法:
我们依次遍历整个序列,每一次求出从第一个数到当前这个数的最长上升子序列,直至遍历到最后一个数字为止,然后再取dp数组里最大的那个即为整个序列的最长上升子序列。我们用dp[i]来存放序列1-i的最长上升子序列的长度,那么dp[i]=max(dp[j])+1,(j∈[1,
i-1]); 显然dp[1]=1,我们从i=2开始遍历后面的元素即可。下面......
阅读全文