首页 > 代码库 > 动态规划 最长子序列
动态规划 最长子序列
有关概念：
最长上升子序列（LIS，Longest Increasing Subsequence），在一个序列中最长的单调递增的子序列
例子：
输入：
2 1 5 3 6 4 8 9 7
输出：
5
（1）第一种解法：
fi表示以第i个数结尾的LIS长度
对于序列中的一个数i，在i前面枚举数j，j满足比i小且fj最大，将i作为j的后继
伪代码&状态转移方程：
f1=1
for i=2...n
for j=1...i-1
if(aj<ai)fi=max(fi,fj+1)
最后结果在f1~fn中取最大值
当然，可以在更新fi的时候顺便记录j的位置，在最后可以输出整个LIS
private static int sequence(int[] array, int n) { if (n == 0) { return 0; } int[] maxLen = new int[n]; // 初始化数组元素值 for (int i = 0; i < n; i++) { maxLen[i] = 1; } for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++) { if (array[j] < array[i]) { // 解最大值，有多条路径 maxLen[i] = Math.max(maxLen[i], maxLen[j] + 1); } } } // 数组升序 Arrays.sort(maxLen); // 数组最大值 return maxLen[n - 1]; }
时间复杂度为o(n^2);
第二种：详情见该博文；http://www.cnblogs.com/ziyi--caolu/p/3227121.html；
动态规划 最长子序列
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。