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

NC91 最长上升子序列(三)

首先用二分的方法找出最大的长度，如例子

[2,1,5,3,6,4,8,9,7]

遍历到 [2]
遍历到1，发现1<-2，则二分出1应该待的位置，也就是第一个大于等于1的数的位置就是2，此时辅助数组剩下[1]
遍历到5，比1大，变为[1,5]
遍历3,比5小，则二分出位置，辅助数组变为[1,3]
遍历6,比3大，辅助数组变为[1,3,6]
....以此类推 最后得到[1,3,7,8,9]这不是最终的答案，这个方法只能够找出最大的长度

此时我们加一个辅助数组记录我们上述的元素组应当在辅助数组中的位置，例子中如下 [2,1,5,3,6,4,8,9,7]
[0,0,1,1,2,2,3,4,2]
这时候不难发现，将第二个数组4,3,2,1,0形式倒推回去，就是我们要求的最小数组，也就是找到最后出现的递减数列。

class Solution {
public:
    /**
     * retrun the longest increasing subsequence
     * @param arr int整型vector the array
     * @return int整型vector
     */
    static const int N = 200050;
    int arr[N];
    vector<int> LIS(vector<int>& arr) {
        int n = arr.size();
        vector<int>a(n+10,-1);
        vector<int>posi(n+10,-1);
        int k = -1;
        for(int i=0;i<n;i++){
           if(arr[i]>a[k]||k==-1){
               a[++k]=arr[i];
               posi[i]=k;
           }else{
               int pos = lower_bound(a.begin(),a.begin()+k,arr[i])-a.begin();
               a[pos]=arr[i];
               posi[i]=pos;
           }
        }
        vector<int>ans;
        int m = k;
        for(int i=arr.size()-1;i>=0;i--){
            if(posi[i]==m)ans.push_back(arr[i]),m--;
        }
        reverse(ans.begin(),ans.end());
        return ans;
    }
};