数组最长递增子序列

public class MaxList {

    //给定arr,返回arr,的最长递增子序列
    //下面该方法对arr中左右子序列从左到右找出每个位置处的最大最序列个数
    public int[] getdp(int[] arr){
        int[] dp = new int[arr.length];
        for(int i = 0; i < arr.length; i++){
            dp[i] = 1;
            for(int j = 0; j < i; j++){
                if(arr[j] < arr[i]){
                    dp[i] = Math.max(dp[i], dp[j]+1);
                }
            }
        }
        return dp;
    }

    //以上拿到从左到右最大子序列的长度和最后一个数的位置
    //一下方法得到最大子序列
    //先找出dp中的最大值index为x，则最大子序列为arr[x]个，如果dp[i] = dp[x]-1,arr[i] < aarr[x]则倒数第二个数为arr[i]

    public int[] generateList(int[] arr, int[] dp){
        int minIndex = 0;
        for(int i = 0; i < dp.length; i++){
            minIndex = minIndex < dp[i] ? minIndex : i;
        }
        int[] res = new int[dp[minIndex]];
        int len = res.length-1;
        res[minIndex-1] = arr[minIndex];
        for(int i = minIndex-1; i > 0; i--){
            if(arr[i] < arr[minIndex] && dp[i] == dp[minIndex]-1){
                res[--len] = arr[i];
                minIndex = i;
            }
        }
        return res;
    }

    public int[] getList(int[] arr){
        int[] dp = getdp(arr);
        return generateList(arr, dp);
    }


    //上述方法的时间复杂度为o(n^2)，改进上述方法，主要再dp数组的获取上，上述过程每次从0到i查询
    //而现在加一个数组ends来记录前面的有效数字，ends更新的逻辑如下：
    // 1.即递增序列，如果碰到比最后一个数字还大，则可以递增那么就把该大数最为最后一个有效数。
    // 2.如果碰到当前数比最后一个数小，那我们在ends中去找他的合适位置，比如ends[0...3] = [1,4,5,8]现在有一个值
    //   7，则找到8的位置，此时当7为序列最后的数时候我们得到的最大子序列的长度是没有变化的即为ends[3]
    //   但是我们希望子序列最后一个数尽可能的小，因为万一后面还有一个8出现我们的子序列不久可以增长了吗？
    //   所以2 的情况为ends更新的情况，而查找的过程为二分查找，比上述遍历节省时间
    public int[] getdp2(int[] arr){
        int[] dp = new int[arr.length];
        int[] ends = new int[arr.length];
        ends[0] = arr[0];
        dp[0] = 1;
        int right = 0, l = 0, r = 0, m = 0;
        for(int i = 0; i < arr.length; i++){
            //初始化二分查找的边界
            l = 0;
            r = right;
            while(l <= r){
                m = (l + r) >> 1;
                if(arr[i] > ends[m]){
                    l = m + 1;
                } else {
                    r = m-1;
                }
                //出现arr[i]>ends[r]的时候l > right；
                right = Math.max(right, l);
                ends[l] = arr[i];
                dp[i] = l+1;
            }
        }
        return dp;
    }
}