问题描述:
找出由n个数组成的序列的最长单调递增子序列
解法一:
原序列记为X,对n个数递增排序,构造一个新序列Y, 对X,Y求其最长公共子序列即可.
/*
* 最长单调递增子序列
* 问题描述:
* 找出由n个数组成的序列的最长单调递增子序列
* 算法设计:
* 解法一:
* 原序列记为X,对n个数递增排序,构造一个新序列Y, 对X,Y求其最长公共子序列即可.
*
* auther:thj
* 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 = {5,2,4,6,5,1,8};
LISLength lis = new LISLength(arr);
List<Integer> a = lis.getLIS();
for (Integer item: a)
{
System.out.print(item + " ");
}
}
}
序列X={5, 2, 4, 6,5,1, 8}
执行结果:
2 4 5 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;
/*
* 最长单调递增子序列
* 问题描述:
* 找出由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:thj
* 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 = {5, 2, 4, 6, 5, 1, 8};
LIS lis = new LIS(a);
lis.lis();
}
}
序列X={5, 2, 4, 6,5,1, 8}
执行结果:
2 4 5 8
分享到:
相关推荐
动态规划:最长单调递增子序列 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的最长单调递增子序列的长度(下标可不连续)
最长单调递增子序列,使用动态规划算法,时间复杂度O(n2)
使用动态规划思想求出最长单调递增子序列(LIS),时间复杂度为O(n log k)
设计一个O(n2)时间的算法,找出由n个数组成的序列的最长单调递增子序列。
最长递增子序列问题是一个很基本、较常见的小问题,但这个问题的求解方法却并不那么显而易见,需要较深入的思考和较好的算法素养才能得出良好的算法。由于这个问题能运用学过的基本的算法分析和设计的方法与思想,...
最长单调递增子序列,运行时间为O(nlgn),为算法导论上的算法
我写的LIS算法,有两种思路,程序全在这个cpp文件中,可以运行
算法导论,请给出一个O(n^2)时间的算法,使之能找出n个数的序列中最长的单调递增子序列
中科大软件学院 算法导论课程实验 正式题目二 最长递增子序列 实验报告 使用4种不同的方式实现最长递增子序列
贪心算法、动态规划实现最长递增子序列的求取(MFC编程)。
动态规划求 最长的单调递增子序列的题目,可。
接着上一个资源,一起发,下面还有
含有2个小实验,包含数塔问题、最长单调递增子序列问题
该ppt讲解了算法导论的第十五章动态规划部分。主要讲述了1.动态规划与分治的区别;2. 通过三个例子棍子切割问题、矩阵链相乘问题和最长公共子序列问题详细描述了动态规划的...3.最后做了一个最长单调递增子序列的练习。
最长单调递增子序列 最长公共子序列 3.回溯法 n后问题 计算排序 计算组合数 图的m着色问题 子集合问题 4.排序 合并排序 快速排序 5.贪心算法 背包问题 活动安排问题 旅行规划问题 汽车加油问题 删除问题 最优装载
最大子串和,最长公共子序列,最长单调递增子序列 图论:二分图的最大匹配,如匈牙利算法(至少需要完成5道题目) 计算几何:(至少需要完成10道题目) 判断点是否在线段上 判断线段相交 判断矩形是否包含点 判断圆...
最大子串和,最长公共子序列,最长单调递增子序列, 图论:二分图的最大匹配,如匈牙利算法 (至少需要完成5道题目) 计算几何:(至少需要完成10道题目) 判断点是否在线段上 判断线段相交 判断矩形是否包含点 判断...
最大子串和,最长公共子序列,最长单调递增子序列, 6、图论:二分图的最大匹配,如匈牙利算法 (至少需要完成5道题目) 7、计算几何:(至少需要完成10道题目) (a)判断点是否在线段上 (b)判断线段相交 (c)...