青岛网站推广外包,济南网站建设询问企优互联价低,wordpress右侧悬浮插件,电子商务网站建设规划方案论文最长递增子序列问题#xff1a;在一列数中寻找一些数#xff0c;这些数满足#xff1a;任意两个数a[i]和a[j]#xff0c;若i
设dp[i]表示以i为结尾的最长递增子序列的长度#xff0c;则状态转移方程为#xff1a;
dp[i] max{dp[j]1}, 1j
这样简单的复杂度为O(n^2)在一列数中寻找一些数这些数满足任意两个数a[i]和a[j]若i
设dp[i]表示以i为结尾的最长递增子序列的长度则状态转移方程为
dp[i] max{dp[j]1}, 1j
这样简单的复杂度为O(n^2)其实还有更好的方法。
考虑两个数a[x]和a[y]x
按dp[t]k来分类只需保留dp[t]k的所有a[t]中的最小值设d[k]记录这个值d[k]min{a[t],dp[t]k}。
这时注意到d的两个特点(重要)
1. d[k]在计算过程中单调不升
2. d数组是有序的d[1]
利用这两个性质可以很方便的求解
1. 设当前已求出的最长上升子序列的长度为len(初始时为1)每次读入一个新元素x
2. 若xd[len]则直接加入到d的末尾且len(利用性质2)
否则在d中二分查找找到第一个比x小的数d[k]并d[k1]x在这里xd[k1]一定成立(性质1,2)。
/**
.最长递增子序列O(nlogn)算法
.状态转移方程f[i] max{f[i],f[j]1},1j
.分析加入xf[y],则x相对于y更有潜力。
.首先根据f[]值分类记录满足f[t]k的最小的值a[t],记d[k]min{a[t]},f[t]k.
. 1.发现d[k]在计算过程中单调不上升
. 2.d[1]
.解法
.1. 设当前最长递增子序列为len,考虑元素a[i];
.2. 若d[len]
. 否则,在d[0-len]中二分查找,找到第一个比它小的元素d[k],并d[k1]a[i].().*//*** Created by guojun on 2015/9/25.*/public class MaxUpSequence {public static void main(String[] args) {int[] a new int[20];for (int i 0; i a.length; i) {a[i] (int)( Math.random() * 100);System.out.print(a[i] \t);}System.out.println();int[] b new int[a.length];b[0] a[0];int len findSeq(a, b);System.out.println(len);}public static int BinarySerch(int key, int[] a, int low, int high) {while (low high) {int mid low (high - low) / 2;if (key a[mid] key a[mid 1]) {return mid1;} else if (key a[mid]) {low mid 1;} else if (key a[mid]) {high mid - 1;}}return 0;}public static int findSeq(int[] a, int[] b) {if (a.length 1) return 1;int len 1;for (int i 1; i a.length; i) {if (a[i] b[len - 1]) {b[len] a[i];len;} else if (a[i] b[len - 1]) {int j BinarySerch(a[i], b, 0, len - 1);b[j] a[i];}}return len;}}
