题解 | #最长上升子序列(三)#

//https://www.nowcoder.com/questionTerminal/9cf027bf54714ad889d4f30ff0ae5481?commentTags=Java

public class Solution {
    /**
     * retrun the longest increasing subsequence
     * @param arr int整型一维数组 the array
     * @return int整型一维数组
     */
    public int[] LIS (int[] arr) {
        // write code here
        //最长有一个 有多个
        int len = 1, n = arr.length;
        if (n == 0) {
            return new int[0];
        }
        //d用来记录长度，和所对应的最大值  最长就是 n  
        int[] d = new int[n+1];
        //记录 i位置的最大递增长度
        int[] w = new int[n];
        d[len] = arr[0];
        w[0] = len;
        for(int i = 1;i<n;i++){
            //如果是递增序列 len , arr[i]
            if(arr[i] > d[len]){
                d[++len] = arr[i];
                w[i] = len;
            }
            else{
                //如果不是 那就从 1到 之前递增间找一个递增的
                int left = 1, right = len, pos = 0;
                while(left <= right){
                     int mid = (left +right) >>1;
                    if(d[mid] < arr[i]) {
                        pos = mid;
                        left = mid +1;
                    }else{
                        right = mid - 1;
                    }
                }
                d[pos+1] = arr[i];
                w[i] = pos +1;
            }
        }
        int[] result = new int[len];
        for(int i = n -1,j = len;j>0;i--){
            if(w[i] == j){
                result[--j] = arr[i];
            }
        }
        return result;
    }
}