寻找最长递增子序列 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();
		
	}

}

评论

2 楼 chriszeng87 2011-05-22  

chenhao112358 写道

用动态规划解决。

确实是动态规划的

1 楼 chenhao112358 2011-05-22  

用动态规划解决。