给定数组arr，返回arr最长递增子序列。

举例：

arr=[2, 1, 5, 3, 6, 4, 8, 9, 7],返回的最长递增子序列是[1,3,4,8,9]。

 

方法：

建立dp[i]数组,每一位表示以这一位结尾的最长递增子序列，然后根据最大值求出子序列。

 

时间复杂度为O(n^2).

代码：

public class Main {    　　//求出dp数组    public static int[] getDP(int[] array) {        if(array==null || array.length==0) {            return null;        }                int len = array.length;        int[] dp = new int[len];        for(int i=0; i
     
      max) {                max = dp[i];                index = i;            }        }        int[] res = new int[max];        res[--max] = array[index];        for(int j=index; j>=0; j--) {            if(array[j]