首页 > 代码库 > 最长【递增】子序列:注意没有公共,即只有一个序列。
最长【递增】子序列:注意没有公共,即只有一个序列。
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])。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。