Give an O(nlgn) time algorithm to find the longest monotonically increasing subsequence of a sequence of n numbers.
(Hint: Observe that the last element of a candidate subsequence of length i is at least as large as the last element of a candidate subsequence of length i-1.
Maintain candidate subsequences by linking them through the input sequence.)
子序列下标不要求是连续的。参考两篇文章：
http://blog.csdn.net/wdq347/article/details/8978394
http://blog.csdn.net/wangche320/article/details/9185919
下面是Java代码。
/**
* The max increasing subsequence must be ended with one(or several) of the array,
* To find the max increasing subsequence, is to find all length subsequences ending with each array member,
* and choose the max length in them.
*/
public static void findLongestIncreaseSubseq(int[] array, int n) { // O(nlgn)
System.out.println(Arrays.toString(array));
int[] preValues = new int[n]; // the previous element of max subsequence for current element
int[] minEnding = new int[n]; // the increasing min ending value of all max subsequence
int minDefValue = -1; // or set to Integer.MIN_VALUE;
for(int k=0; k<n; k++) {
minEnding[k] = minDefValue;
preValues[k] = minDefValue;
}
int maxLen = 1; // the length of max subsequence
int maxIndex = 0; // the index of last element of max subsequence
minEnding[0] = array[0];
for(int i=1; i<n; i++) { // 依次寻找以 array[i]结尾的递增子序列
//在所有子序列的最小结束元素数组中找到array[i]的插入位置
int pos = findPosByBinarySearch(minEnding, 0, maxLen, array[i]);
if( pos == maxLen ){
minEnding[pos] = array[i];
maxLen ++;
maxIndex = i;
// set the former when find longer subsequence ending with current element
preValues[i]=minEnding[pos-1];
}
else {
if(array[i] <= minEnding[pos]) { //if equal, the later still replace the former
minEnding[pos] = array[i];
// current element is smaller then previous subsequence
preValues[i] = minDefValue;
}
else { // if(array[i] > minEnding[pos])
// the former is minEnding[pos] for the subsequence ending with current element
preValues[i] = minEnding[pos];
}
}
}
// maxLen is the length of using minEnding
System.out.println("max len:"+maxLen);
System.out.println("minEndings:\n" + Arrays.toString(minEnding));
System.out.println("max index:"+maxIndex);
System.out.println("preValues:\n" + Arrays.toString(preValues));
Queue<Integer> maxSeqQueue = new ArrayDeque<Integer>();
for(int index=0; index < preValues.length; index++) {
if(preValues[index] != minDefValue) {
maxSeqQueue.offer(preValues[index]);
}
}
maxSeqQueue.offer(array[maxIndex]);
System.out.println("max subsequence:\n"+maxSeqQueue);
}
/**
* The minEnding is sorted array to store the min value of all length subsequences,
* the index=0 means the increasing subsequence length is 1.
*/
static int findPosByBinarySearch(int[] minEnding, int start, int length, int value) {
int end = length -1;
if(value > minEnding[end]) { //若value大于最大子序列最小值，返回length
return length;
}
if(value < minEnding[start]) { // 若value小于最小子序列最小值，返回0
return start;
}
// find the insert position for element by binary search O(lgn)
while(start <= end) {
int mid = (start+end) >>> 1; // 无符号右移
if(minEnding[mid] == value) {
return mid;
}
else if(minEnding[mid] < value) {
start = mid +1;
}
else if(minEnding[mid] > value) {
end = mid -1;
}
}
return start; // return the start position if not find equal one
}
public static void main(String[] args) {
int[] array = { 4, 2, 3, 7, 6, 12, 5 };
findLongestIncreaseSubseq(array, array.length);
int[] array1 ={0,1,3,5,1,4,6,7,0,8,9,2};
findLongestIncreaseSubseq(array1, array1.length);
int[] array2 ={2,1,3,0,4,1,5,2,7};
findLongestIncreaseSubseq(array2, array2.length);
}
算法导论 15.4-5 求一个n个数的序列的最长单调递增子序列 子序列下标不要求是连续的
Give an O(n^2) time algorithm to find the longest monotonically increasing
subsequence of a sequence of n numbers.
// find longest increase subsequence with dynamic programming
public static void getLongestIncreaseSubseq(int[] array, int n) { // O(n^2)
System.out.println(Arrays.toString(array));
int[] maxLengths = new int[n]; // the max length of current longest sequence
int[] lastIndexs = new int[n]; // index of last element of longest sequence
for(int k=0; k<n; k++) {
maxLengths[k] = 1; // at least length is 1, and previous set to -1
lastIndexs[k] = -1;
}
int maxLen = 1;
int maxIndex = 0;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
//循环比较当前元素和其之前所有元素
if (array[i] > array[j]) { //若比前面的元素大，是一个单增子序列中的元素
if (maxLengths[i] < maxLengths[j] + 1) { // 若当前子序列长度 < 前面元素的子序列长度+1
maxLengths[i] = maxLengths[j] + 1;
lastIndexs[i] = j; // 若是子序列中的元素，记录比第i个数小的第j个数的下标
}
}
}
if(maxLengths[i] > maxLen) {
maxLen = maxLengths[i];
maxIndex = i;
}
}
System.out.println("longest subsequence length:" + maxLen);
System.out.println("longest subsequence last index:" + maxIndex);
// System.out.println(Arrays.toString(maxLengths));
// System.out.println(Arrays.toString(lastIndexs));
System.out.println("longest subsequence:");
Deque<Integer> stack = new ArrayDeque<Integer>();
int k=maxIndex;
for(; maxLengths[k] > 1; ) {
stack.push(array[k]);
k = lastIndexs[k];
}
stack.push(array[k]);
System.out.println(stack);
}