最长递增子序列

 

求数组中最长递增子序列

写一个时间复杂度尽可能低的程序，求一个一维数组（N个元素）中的最长递增子序列的长度。

例如：在序列1，-1，2，-3，4，-5，6，-7中，其最长的递增子序列为1，2，4，6。

public class LongestIncreasingSequence {

	/**
	 *求数组中最长递增子序列
              写一个时间复杂度尽可能低的程序，求一个一维数组（N个元素）中的最长递增子序列的长度。
              例如：在序列1，-1，2，-3，4，-5，6，-7中，其最长的递增子序列为1，2，4，6
	 */
	public static void main(String[] args) {
		int[] A = {1,-1,2,-3,4,-5,6,-7};
		LAS(A);
	}

	public static int LAS(int[] A){
		int length = A.length;
		int B[] = new int[length];
		B[0] = 1;
		int max = 1;
		for(int i=1;i<length;i++){
			int _max = 0;  //记录当前元素中比它小的元素的B[i]值最大的一个，这里只能设置为0而不能设置为1 
			int index = i;  //找出当前元素中比它小的元素，并比较B[i]值，记录最大的B[i]值的索引
			for(int j=i-1;j>=0;j--){
				if(A[j]<A[i] && B[j] > _max){
					_max = B[j];
					index = j;
				}				
			}
			if(index == i)   //索引没变，前面没有比它小的元素了，则值为1
				B[i] = 1;
			else
				B[i] = B[index] + 1;   //索引变了，则+1
			if(B[i] > max)
				max = B[i];
				
		}
		for(int i=0;i<length;i++)
			System.out.print(B[i]+ " ");
		
		System.out.println("\nThe Max Length is : " + max);
		return max;
	}
}