题解 | #最长递增子序列#

动态规划二分优化
时间复杂度

把arr[]向右偏移为下标从1开始的a[]
g[i]为长度为i的最长上升子序列的最小的末尾元素的下标
last[i]表示以第i个元素结束的最长上升子序列的上一个元素的下标

const int N = 100010;
class Solution {
public:
    /**
     * retrun the longest increasing subsequence
     * @param arr int整型vector the array
     * @return int整型vector
     */

    int g[N], a[N], last[N];
    vector<int> LIS(vector<int>& arr) {
        memset(g, 0, sizeof g);
        int n = arr.size(), len = 0;

        a[0] = -1;
        for(int i = 1; i <= n; i ++)
        {
            a[i] = arr[i - 1];

            int l = 0, r = len;
            while(l < r)
            {
                int mid = l + r + 1 >> 1;
                if(a[i] > a[g[mid]])  l = mid;
                else  r = mid - 1;
            }
            last[i] = g[l];
            g[l + 1] = i;
            if(l + 1 > len)  len ++;

            //for(int i = 1; i <= len; i ++)  printf("%d ", a[g[i]]);  puts("");
        }
        vector<int> res;
        for(int i = g[len]; i; i = last[i])  res.push_back(a[i]);
        reverse(res.begin(), res.end());
        return res;
    }
};