编程之美2.16 数组中最长递增子序列的长度 O(nlgn)

题目:

       设L=<a1,a2,…,an>是n个不同的实数的序列，L的递增子序列是这样一个子序列Lin=<aK1,ak2,…,akm>，其中k1<k2<…<km且aK1<ak2<…<akm。求最大的m值。

 

 

在下面的代码中

lis[i]表示以array[i]结尾的递增子序列的最大长度，

max[j]表示长度为j的递增子序列的最大元素的最小值，

则max[lis[i]]表示长度为lis[i]的递增子序列的最大元素的最小值，即array[i].

 

package beautyOfProgram;

public class LIS {

	int  INT_MIN = -1000000;

	public int binary_search(int[] a,int len,int n)//若返回值为x,则a[x]>=n>a[x-1]
	{
		int left=0,right=len-1,mid=(left+right)/2;
	    while(left<=right)
	    {
	        if(n>a[mid]) left=mid+1;
	        else if(n<a[mid]) right=mid-1;
	        else return mid;
	        mid=(left+right)/2;
	    }
	    return left;

	}

	public int lis(int[] arr, int len)
	{
		int[] max = new int[len+1];
		int[] lis = new int[len];

		max[0] = INT_MIN;
		max[1] = arr[0];
		int maxLis = 1;
		for(int i=0;i<len;i++)
		{
			
			//遍历
			/*for(int j=maxLis;j>=0;j--)
			{
				if(arr[i] > max[j])
				{
					lis[i] = j+1;
					break;
				}
			}*/

			//二分查找
			lis[i] = binary_search(max,maxLis+1,arr[i]);

			if(lis[i] > maxLis) //arr[i]大于前面所有的数
			{
				max[lis[i]] = arr[i];
				maxLis = lis[i];
			}
			else if(max[lis[i]-1] < arr[i] && arr[i] < max[lis[i]])
			{//arr[i]比当前最长的子序列的最后一个小，比它前面一个又大
				max[lis[i]] = arr[i];
			}
		}

		return maxLis;
	}
	
	public static void main(String[] args) 
	{
		int arr[] = {1,-1,2,-3,4,-5,6,-7};//{1,2,5,4,6};
		LIS l = new LIS();
		System.out.println(l.lis(arr,arr.length));
	}

}