连续上升子序列

这道题真的很不错，要求最长的子序列，而不是长度，而且题目设置了必须得
nlogn的复杂度才能过。
如果暴力的话，只需要知道最大子序列长度和以下标i元素为结尾的子序列最大长度。但是这种办法在
dp时只能暴力，如果想二分查找，必须得知道每个长度的序列里的最后一个元素的最小值。因此需要
维护两个数组和一个len。
我觉得这题在leetcode完完全全是hard级别

import java.util.*;


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];
        }
        int[] d = new int[n + 1];
        int[] w=new int[n];
        d[len] = arr[0];
        w[0] = len;
        for (int i = 1; i < n; ++i) {
            if (arr[i] > d[len]) {
                d[++len] = arr[i];
                w[i]=len;
            } else {
                int l = 1, r = len, pos = 0;
                while (l <= r) {
                    int mid = (l + r) >> 1;
                    if (d[mid] < arr[i]) {
                        pos = mid;
                        l = mid + 1;
                    } else {
                        r = mid - 1;
                    }
                }
                 d[pos + 1] = arr[i];
                 w[i]=pos+1;
            }
        }
        int[] res=new int[len];
        for(int i=n-1,j=len;j>0;--i){
            if(w[i]==j){
                res[--j]=arr[i];
            }
        }
        return res;
    }
}