首页 > 代码库 > 最长【递增】子序列:注意没有公共,即只有一个序列。

最长【递增】子序列:注意没有公共,即只有一个序列。

monotonic:单调的.

序列为X=(x1,x2,x3,x4...),首先排序X得到X‘,找出X和X‘的最长公共子序列(LCS)即可。

 

 

另一种思维:

 先回顾经典的O(n^2)的动态规划算法,设A[i]表示序列中的第i个数,F[i]表示从1到i这一段中以i结尾的最长上升子序列的长度,初始时设F[i] = 0 ;(i = 1, 2, ..., len(A))。则有动态规划方程:F[i] = max{1, F[j] + 1} (j = 1, 2, ..., i - 1, 且A[j] < A[i])。