问题描述:给出一个数列,找出其中最长的单调递减(或递增)子序列。
解题思路:动态规划。假设0到i-1这段数列的最长递减序列的长度为s,且这些序列们的末尾值中的最大值是t。对于a[i]有一下情况:
(1) 如果a[i]比t小,那么将a[i]加入任何一个子序列都会使0到i的最长单调序列长度变成s+1,这样的话,在0到i的数列中,长度为s+1的递减子序列的末尾值最大值就是a[i];
(2) 如果a[i]和t相等,那么说明数列从0项到i项的最长单调子序列长度就是s;
(3) 如果a[i]比t大,那么a[i]就不一定能够成为长度为s的递减子序列的末项,这取决于长度为s-1的各个递减子序列的末尾值的最大值t'。
如果t'比a[i]要大,那么就可以形成长度为s的递减子序列,如果t'比a[i]小,那么问题就在往前递推,把a[i]和长度为s-2的各个递减子序列的末尾值的最大值比较,直到:(1) a[i]比长度为s'的递减子序列的末尾值的最大值要小,那么a[i]就是数列0到i部分长度为s'+1的递减子序列的末尾值中的最大值;(2) a[i]比任何长度的递减子序列的末尾值的最大值都要大,那么a[i]就是长度为1的递减子序列的最大值。
所以,引入数组c[i]表示长度为i的递减子序列的末尾值的最大值。显然c数组必然是单调递减的。b[i]数组用于子序列的输出,b[i]表示从a[0]到a[i]且终止于a[i]的最长递减序列的长度。
算法复杂度:O(nlogn),对于数组c的查找使用二分查找,降低了整体的算法复杂度。
算法步骤:
1) 读入n和a[i].
2) 将数组c全部赋值为-1.
3) 定义变量s,初始化为1,s表示目前为止最长单调序列的长度,同时也是数组C的有效容量。c[1] = a[0].
4) 对于0到n-1的每个i:
查找c[1]到c[s],找到一个值k满足下列几种情况:
(1)c[k] <= a[i] 而 c[k-1] > a[i] (如果k>1)
(2)找不到(1)中k的话,k等于s+1,并且s自加一。
c[k] = a[i];
b[i] = k;
5) 最后所得s即为所求值。
import java.util.Scanner;
public class LongestSubSeq {
public static int bsearch(int[] a, int s, int m) {
int low = 1;
int high = s;
int mid;
while (low < high) {
mid = (low + high) / 2;
if (a[mid] == m )
return mid;
if (a[mid] > m)
low = mid + 1;
else
high = mid;
}
if (a[low] <= m)
return low;
else
return low+1;
}
public static void print(int[] a, int[] b, int level, int start) {
if (level == 0)
return;
int i = start;
while (b[i] != level)
i--;
print(a, b, level-1, i-1);
System.out.print(a[i] + " ");
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] array = new int[n];
int[] b = new int[n];
int[] c = new int[n+1];
for (int i = 0; i < n; i++) {
array[i] = in.nextInt();
c[i] = -1;
}
int s = 1;
int k;
c[1] = array[0];
for (int i = 0; i < n; i++) {
k = bsearch(c, s, array[i]);
if(k > s)
s++;
c[k] = array[i];
b[i] = k;
}
System.out.println("The length of longest squence is: " + s);
System.out.print("The squence is: ");
print(array, b, s, n-1);
}
}
分享到:
相关推荐
动态规划:最长单调递增子序列 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. ...
用动态规划方法找出由n个数a【i】(1)组成的序列的一个最长单调递增子序列
L={a1,a2,a3,…,an},是由n个不同的实数组成的序列,求L的最长单调递增子序列的长度(下标可不连续)
最长单调递增子序列,使用动态规划算法,时间复杂度O(n2)
使用动态规划思想求出最长单调递增子序列(LIS),时间复杂度为O(n log k)
设计一个O(n2)时间的算法,找出由n个数组成的序列的最长单调递增子序列。
动态规划求 最长的单调递增子序列的题目,可。
贪心算法、动态规划实现最长递增子序列的求取(MFC编程)。
最长递增子序列问题是一个很基本、较常见的小问题,但这个问题的求解方法却并不那么显而易见,需要较深入的思考和较好的算法素养才能得出良好的算法。由于这个问题能运用学过的基本的算法分析和设计的方法与思想,...
我写的LIS算法,有两种思路,程序全在这个cpp文件中,可以运行
最长单调递增子序列,运行时间为O(nlgn),为算法导论上的算法
算法导论,请给出一个O(n^2)时间的算法,使之能找出n个数的序列中最长的单调递增子序列
中科大软件学院 算法导论课程实验 正式题目二 最长递增子序列 实验报告 使用4种不同的方式实现最长递增子序列
算法之动态规划---单调递增子序列,和图像压缩算法
acm模板(村村通,一笔画,最长单调不升序列等) ...给定一个n个元素的数列a1,a2,…,an,求该序列中单调不升序列中最长者的长度。如34,78,53,36,40的最长单调不升序列有78,53,36或78,53,40,长度都是3。
适合初学者,经典DP
接着上一个资源,一起发,下面还有
有两张单调递增有序的线性表A和B-采用顺序存储结构-将这两张表合并成C表-要求C表单调递减有序。Wo.pdf
对于算法 单调序列问题的创新解法 c++实现单调序列问题:给定一个正整数n,求出对于n个整数集合{1,2,3,…,n-1,n}所有的排列中,单调序列的数量。
给定一个单调递增的整数序列,问某个整数是否在序列中