最长递增子序列

题目：一个数组{2,1,5,3,6,4,8,9,7}，找出最长递增子序列。

dp[i]=max{dp[i],dp[j]+1(0<=j<i,array[j]<array[i])}

public static void main(String[] args){
		int[] array={2,1,5,3,6,4,8,9,7};
		int[] dp=build(array);
		System.out.println(Arrays.toString(max(array,dp)));
	}
	public static int[] build(int[] array){
		int[] dp=new int[array.length];
		if(array==null || array.length<1){
			return dp;
		}
		for(int i=0;i<array.length;i++){
			dp[i]=1;
			for(int j=0;j<i;j++){
				if(array[j]<array[i]){
					dp[i]=Math.max(dp[i], dp[j]+1);
				}				
			}
		}
		return dp;
	}
	public static int[] max(int[] array,int[] dp){
		int len=0;
		int index=0;
		for(int i=0;i<dp.length;i++){
			if(dp[i]>len){
				len=dp[i];
				index=i;
			}
		}
		int[] number=new int[len];
		number[--len]=array[index];
		for(int i=index;i>=0;i--){
			if(array[i]<array[index]&&dp[index]-dp[i]==1){
				number[--len]=array[i];
				index=i;
			}
		}
		return number;
	}