寻找最长递增子序列 O(nlgn)算法
题目:
设L=<a1,a2,…,an>是n个不同的实数的序列，L的递增子序列是这样一个子序列Lin=<aK1,ak2,…,akm>，其中k1<k2<…<km且aK1<ak2<…<akm。求最大的m值。
?
算法思想(参考http://hi.baidu.com/silverxinger/blog/item/571e7cdb996d1c02632798ad.html
和?http://topic.csdn.net/t/20030731/21/2095180.html):
数组l[i] ? 记录 ? 长度为i的 ? 递增子串 ? 的 ? 最后一个元素?
对于某元素a[k], ? 当a[k]> l[i] ? ? -> ? ? l[i+1]=a[k] ? ??
若i是 ? 满足a[k]> l[i] ? 的最大整数， ? i+1就是以a[k]结尾的最大递增子串长?
a有n个元素,扫一遍,O(n);查找l[i]用二分查找,O(logn)?
?
?
代码实现:
?
package introtoalgo;import java.util.ArrayList;import java.util.List;import java.util.Vector;public class Incre {private static int[] array = //{1, 9, 3, 8, 11, 4, 5, 6, 4, 19, 7, 1, 7 };//{5,3,6,7,8,4,1};{1 , -1 , 2 , -3 , 4 , 3 , 0 ,-5 , 6 ,7};private static Vector<Integer> tempResult = new Vector<Integer>();//tempResult[i]表示长度为i的序列的最小下标对应的值，如当 i=5时，tempResult = {1,3,4,11}private static int maxLength = 1; //当前最长长度private static int[] mem = new int[array.length]; //mem[i] 表示以array[i]结尾的最长递增子序列的长度private static int findTheFirstLarger( int i ) { //从当前最长递增子序列中找到第一个大于array[i]的数int left = 1, right = tempResult.size()-1;while( left <= right ) {int mid = (left + right) / 2;if(array[i] < tempResult.get(mid)) {right = mid - 1;}else if(array[i] == tempResult.get(mid)) {return mid; //重复元素}else{left = mid + 1;}}return left;}public static void findLongestIncre() {mem[0] = 1;//以array[0]结尾的最大子串长tempResult.add(array[0]);//这个只是用来占位置tempResult.add(array[0]);//长度为1的递增子序列的最后一个元素for(int i=1; i<array.length; i++) {int firstLargerNo = findTheFirstLarger(i);if(firstLargerNo >= tempResult.size()) {tempResult.add(array[i]);mem[i] = tempResult.size()-1;}else { mem[i] = firstLargerNo;if(array[i] == tempResult.get(firstLargerNo)) { //用来处理出现重复元素的情况continue;}tempResult.set(firstLargerNo, array[i]); //修改长度为firstLargerNo的最小下标对应的值} }maxLength = tempResult.size()-1;int[] result = new int[maxLength];result[maxLength-1] = tempResult.get(maxLength);//result.remove(0);int k;//for(k=0; k< array.length; k++)//System.out.print(mem[k]+" ");//System.out.println();System.out.println("Max Length = " + maxLength);int j = array.length - 2;int n = maxLength-1;while(n>0 && j>0) {if(mem[j] == n) {result[n-1] = array[j];n--;}j--;}for(k=0; k< maxLength; k++)System.out.print(result[k]+" ");//return result;}public static void main(String[] args) {findLongestIncre();}} 1 楼 chenhao112358 2011-05-22 用动态规划解决。 2 楼 chriszeng87 2011-05-22 chenhao112358 写道用动态规划解决。确实是动态规划的