问题描述

设有由 n 个不相同的整数组成的数列，记为: a(1)、a(2)、... 、a(n) 且 a(i)<>a(j) (i<>j) 。例如 3，18，7，24，10，12，23，41，16，24 。若存在 i1 < i2 < i3 < ... < ie且有a(i1) < a(i2)< ... <a(ie) 则称为长度为 e 的不下降序列。如上例中 3 ，18 ，24 就是一个长度为 3 的不下降序列，同时也有3，7，10，12，16，24 长度为 6 的不下降序列。程序要求，当原数列给出之后，求出最长的不下降序列。

分析

分析题意得出：已知原序列，求它的最长不下降子序列。我们把已知数据，画出样例图示如下：

1. 根据图上我们发现，子序列中若存在第7个数，它可以描述成：dp[7]=max(dp[1],dp[2],dp[3],dp[5],dp[6])+1

2. 我们令 dp[i] 表示：以 A[i] 结尾的最长不下降子序列长度。这样对 A[i] 来说就会有两种可能：

   1. 如果存在 A[i] 之前的元素 A[j] (j < i)， 满足 A[j] <= A[i] 且 dp[j] + 1 > dp[i] （即把 A[i] 跟在以 A[j] 结尾的LIS后面时能比当前以 A[i] 结尾的LIS长度更长），那么就把A[i]跟在以 A[j]结 尾的 LIS 后面，形成一条更长的不下降子序列 (令 dp[i] = dp[j] + 1)。 即：　dp[i]=max{dp[j]+1} ( A[j]<=A[i] )
   2. 如果 A[i] 之前的元素都比A[i]大，那么A[i]就只好自己形成一条长度为1的LIS序列,即这个子序列里面只有一个A[i]。即： A[i]=1

最后以 A[i] 结尾的 LIS 长度就是 1,2 中能形成的最大长度。

状态转移方程

   dp[i] = max{1,dp[j]+1} (j = 1,2,…,i-1 && A[j] < =A[i])

显然 dp[i] 只与小于 i 的 j 有关，因此只要让 i 从小到大遍历即可求出整个 dp 数组。

由于 dp[i] 表示的是以 A[i] 结尾的LIS长度，因此从整个 dp 数组中找出最大的那个才是要寻求的整个序列的 LIS 长度，整体复杂度为 O(n^2)。

即： ans=max(dp[i] ) (i=1~n)