最长单调递增子序列——动态规划

题目描述：

给定一个序列X[0···n]，找出它的最长的单调递增子序列（Longest Increasing Subsequence）

解题思路：

使用动态规划方法。
对于i= 1， 2， ……，n，考虑以xi作为最后项的最长递增子序列的长度C[i].
如果在xi项前面存在xj < xi ， 那么 C[i] = max{C[j]} +1；否则，C[i] = 1.
因此，

C[i] = max{C[j]} + 1, 存在j,1<=j<i, xj<xi
C[i] = 1, 所有j,1<=j<i, xj>xi
C[1] = 1

在计算C[i]的时候，用k[i] 记录C[i]取得最大值时候j的值。
如果不存在这样的j，令k[i] = 0。
这个记录用于追踪解。
所求的最长递增子序列的长度是：

C = max{C[i] | i=1,2,……,n}

对于每个i，需要检索比i小的所有的j，需要O(n)的时间，i的取值有n种，所以算法时间复杂度是：
W(n) = O（n^2）