- 浏览: 30691 次
- 性别:
- 来自: 西安
最新评论
问题描述:
找出由n个数组成的序列的最长单调递增子序列
解法一:
原序列记为X,对n个数递增排序,构造一个新序列Y, 对X,Y求其最长公共子序列即可.
/* * description: 最长单调递增子序列 * 问题描述: * 找出由n个数组成的序列的最长单调递增子序列 * 算法设计: * 解法一: * 原序列记为X,对n个数递增排序,构造一个新序列Y, 对X,Y求其最长公共子序列即可. * * auther:cm * date:2010/11/17 */ import java.util.LinkedList; import java.util.List; public class LISLength { private int[] arrX; private int[] arrY; private int[][] c; public LISLength(int[] arr) { arrX = new int[arr.length + 1]; arrY = new int[arr.length + 1]; System.arraycopy(arr,0,arrX,1,arr.length); System.arraycopy(arr,0,arrY,1,arr.length); selectSort(arrY, arrY.length - 1); lisLength(); } //计算最长公共子序列 public void lisLength() { c = new int[arrX.length][arrY.length]; for (int i = 1; i < arrX.length; i++) { for (int j = 1; j < arrY.length; j++) { if (arrX[i] == arrY[j]) { c[i][j] = c[i-1][j-1] + 1; } else { c[i][j] = max(c[i-1][j], c[i][j-1]); } } } } //返回最长单调递增子序列 public List<Integer> getLIS() { LinkedList<Integer> list = new LinkedList<Integer>(); int i = arrX.length - 1; int j = arrY.length - 1; while (i >= 1 && j >= 1) { if (arrX[i] == arrY[j]) { list.addFirst(Integer.valueOf(arrX[i])); i--; j--; } else { if (c[i-1][j] > c[i][j-1]) { i--; } else { j--; } } } return list; } private int max(int m, int n) { return m > n ? m : n; } //选择排序,0号空间不用 private void selectSort(int[] a, int n) { for (int i = 1; i < n; i++) { int k = i; for (int j = i + 1; j <= n; j++) { if (a[k] > a[j]) { k = j; } } if (k != i) { int temp = a[k]; a[k] = a[i]; a[i] = temp; } } } public static void main(String[] args) { int[] arr = {4, 2, 3, 1, 8}; //int[] arr = {8,9,10,2,3,4,5,6}; LISLength lis = new LISLength(arr); List<Integer> a = lis.getLIS(); for (Integer item: a) { System.out.print(item + " "); } } }
序列X={4, 2, 3, 1, 8}
执行结果:
2 3 8
解法二:
1)用一个数组b[n]记录以a[i]结尾的最长单调递增子序列的长度;
2)序列的a的最长单调子序列的长度为max{b[i],0=<i<n};
3)b[i] = max{b[k],a[k]<=a[i]&&0=<k<i} + 1 ,b[0] = 1;
/* * description:最长单调递增子序列 * 问题描述: * 找出由n个数组成的序列的最长单调递增子序列 * 算法设计: * 解法二: * 1)用一个数组b[n]记录以a[i]结尾的最长单调递增子序列的长度; * 2)序列的a的最长单调子序列的长度为max{b[i],0=<i<n}; * 3)b[i] = max{b[k],a[k]<=a[i]&&0=<k<i} + 1 ,b[0] = 1; * * auther:cm * date:2010/11/17 */ public class LIS { private int[] a; private int[] b; public LIS(int[] a) { this.a = a; b = new int[a.length]; } public void lis() { b[0] = 1; for (int i = 0; i < a.length; i++) { int k = 0; for (int j = 0; j < i; j++) { if (a[j] <= a[i] && k < b[j]) { k = b[j]; } } b[i] = k + 1; } int k = max(b); //输出结果 print(k); } //求数组中最大值下标 private int max(int[] b) { int max = b[0]; int k = 0; for (int i = 0; i < b.length; i++) { if (max < b[i]) { max = b[i]; k = i; } } return k; } //输出 public void print(int k) { for (int i = k - 1; i >= 0; i--) { if (b[k] == b[i] + 1 && a[i] <= a[k]) { print(i); break; } } System.out.print(a[k] + " "); } public static void main(String[] args) { int[] a = {4, 2, 3, 1, 8}; LIS lis = new LIS(a); lis.lis(); } }
序列X={4, 2, 3, 1, 8}
执行结果:
2 3 8
发表评论
-
求组合数
2011-03-26 20:23 726求组合数 从n个数里面取m个数 (递归实现) /** ... -
背包问题
2010-12-14 18:27 910与0-1 背包问题类似,所 ... -
0-1背包问题
2010-12-14 18:00 12070-1背包问题: 给定n种物品和一背包。物品i的重量是wi, ... -
装载问题
2010-12-12 18:16 1383装载问题 有一批共n个集装箱要装上两艘载重量分别为c1和c2 ... -
最优装载问题
2010-12-12 11:13 1474问题描述: 有一批集装箱要装上一艘载重量为C的轮船,要求在装 ... -
喝汽水问题
2010-11-28 21:51 913问题描述: 1元钱一瓶汽水,喝完后两个空瓶换一瓶汽水,问:你 ... -
最大子段和(三)
2010-11-21 10:04 686最大子段和问题 解法三: 算法分析: 对于序列a,设j代 ... -
最大子段和(二)
2010-11-20 19:15 824最大子段和问题 解法二:分治法 算法分析: 最大子 ... -
最大子段和(一)
2010-11-20 10:31 895问题描述: 给定n个整数(可能为负数)组成的序列a1,a2, ... -
动态规划之最长公共子序列
2010-11-18 14:25 1355一个给定序列的子序列是在该序列中删去若干元素后得到的序列。若给 ... -
矩阵连乘问题
2010-11-16 21:39 1079/* description: * * 动态规划算法之 ... -
二分搜索法的简单实现
2010-10-20 09:11 638二分搜索算法是运用分治策略的典型例子。 基本思想:将n个元素 ... -
最小生成树之Prim算法
2010-10-16 22:45 965Prim算法Java朴素版 //Prim算法求最小生成树,使 ...
相关推荐
动态规划:最长单调递增子序列 A numeric sequence of ai is ordered if a1 (a1, a2, ..., aN) be any sequence (ai1, ai2, ..., aiK), where 1 , sequence (1, 7, 3, 5, 9, 4, 8) has ordered subsequences, e. ...
L={a1,a2,a3,…,an},是由n个不同的实数组成的序列,求L的最长单调递增子序列的长度(下标可不连续)
用动态规划方法找出由n个数a【i】(1)组成的序列的一个最长单调递增子序列
最长单调递增子序列,使用动态规划算法,时间复杂度O(n2)
使用动态规划思想求出最长单调递增子序列(LIS),时间复杂度为O(n log k)
动态规划求 最长的单调递增子序列的题目,可。
设计一个O(n2)时间的算法,找出由n个数组成的序列的最长单调递增子序列。
算法导论,请给出一个O(n^2)时间的算法,使之能找出n个数的序列中最长的单调递增子序列
最长单调递增子序列,运行时间为O(nlgn),为算法导论上的算法
贪心算法、动态规划实现最长递增子序列的求取(MFC编程)。
最长递增子序列问题是一个很基本、较常见的小问题,但这个问题的求解方法却并不那么显而易见,需要较深入的思考和较好的算法素养才能得出良好的算法。由于这个问题能运用学过的基本的算法分析和设计的方法与思想,...
中科大软件学院 算法导论课程实验 正式题目二 最长递增子序列 实验报告 使用4种不同的方式实现最长递增子序列
我写的LIS算法,有两种思路,程序全在这个cpp文件中,可以运行
接着上一个资源,一起发,下面还有
含有2个小实验,包含数塔问题、最长单调递增子序列问题
该ppt讲解了算法导论的第十五章动态规划部分。主要讲述了1.动态规划与分治的区别;2. 通过三个例子棍子切割问题、矩阵链相乘问题和最长公共子序列问题详细描述了动态规划的...3.最后做了一个最长单调递增子序列的练习。
最长单调递增子序列 最长公共子序列 3.回溯法 n后问题 计算排序 计算组合数 图的m着色问题 子集合问题 4.排序 合并排序 快速排序 5.贪心算法 背包问题 活动安排问题 旅行规划问题 汽车加油问题 删除问题 最优装载
最大子串和,最长公共子序列,最长单调递增子序列 图论:二分图的最大匹配,如匈牙利算法(至少需要完成5道题目) 计算几何:(至少需要完成10道题目) 判断点是否在线段上 判断线段相交 判断矩形是否包含点 判断圆...
最大子串和,最长公共子序列,最长单调递增子序列, 图论:二分图的最大匹配,如匈牙利算法 (至少需要完成5道题目) 计算几何:(至少需要完成10道题目) 判断点是否在线段上 判断线段相交 判断矩形是否包含点 判断...
最大子串和,最长公共子序列,最长单调递增子序列, 6、图论:二分图的最大匹配,如匈牙利算法 (至少需要完成5道题目) 7、计算几何:(至少需要完成10道题目) (a)判断点是否在线段上 (b)判断线段相交 (c)...