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

public class Solution {
    /**
     * retrun the longest increasing subsequence
     * @param arr int整型一维数组 the array
     * @return int整型一维数组
     */
    public int[] LIS (int[] arr) {
        // write code here
        //特判空情况，方便后面处理
        if (arr.length == 0) return new int[0];
        int n = arr.length;
        
        int[] ls = new int[n];    // ls 数组里面存放递增子序列
        int[] dp = new int[n];    // dp 数组里存放以元素i结尾的最大递增子序列长度
        
        ls[0] = arr[0];
        dp[0] = 1;
        int l = 1;    //ls递增序列的实际长度
        
        for (int i = 1; i < arr.length; i++) {
            if (ls[l - 1] < arr[i]) {
                ls[l++] = arr[i];    //直接加入序列
                dp[i] = l;    // dp[i] 对应的序列是整个ls
            } else {
                int j = 0, k = l - 1;
                int idx = 0;
                //找 ls 中第一个 >= arr[i]的（必定存在，因为保证 ls 的最后一个 >= arr[i]）
                while (j <= k) {
                    int m = j + (k - j) / 2;
                    if (ls[m] >= arr[i]) {
                        idx = m;
                        k = m - 1;
                    } else j = m + 1;
                }
                ls[idx] = arr[i];    //找到位置后替换掉，注意是替换不是插入
                // ls 序列的总长不变，但是为了复用原序列一些 < arr[i] 的结果，选择二分把 arr[i] 替换到合适的位置
                //所以 dp[i] 对应的序列其实是 ls 的 [0,idx] 部分（要保证序列的最后是arr[i]），即长度为idx + 1
                dp[i] = idx + 1;
            }
        }
        
        //这里其实可以复用ls来填充的，但是用ans是为了说明求最后的子序列和ls无关
        //ls只是为了上面求dp的复杂度从O(n ^ 2)降低为O(n * logn)
        //这里的求法是倒着遍历，找到满足长度的dp就记录，然后更新。（即同样值的dp，选尽量靠右边的）
        int[] res = new int[l];
        for (int i = n - 1, j = l; i >= 0; i--) {
            if (dp[i] == j) res[--j] = arr[i];
        }
        
        return res;
    }
}