最长上升子序列(三)（动态规划）

题意

给定一个正整数数组，求它的最长上升子序列，如果有多个，求数值字典序最小的

思路分析

上升子序列

先不考虑最长，先考虑如何找到一个上升子序列

每次对于一个值，去找它前面比它小的值就能构成

最后把链输出就能得到上升子序列

for(int i = 0;i<arr.size();i++){
    int j = i-1;
    while(j >= 0 && arr[j] >= arr[i])j--; // 忽略掉 大于等于 当前值的
    prei[i] = j; // 建立链表 指向一个比它小的位置
}

这样每个pre[i]指向了一个比i位置小的又在i之前的位置

如果没有比它小的，那么指向-1

最长上升子序列

上面的做法虽然找到了上升，但是没法得到最长，例如1 2 1 3, 会让3指向前一个1，而不是指向2

为了解决这个问题，可以增加一个记录长度的数组len[i],表示到i为止的最大长度为多少，这样不光找比它小还要找最长

for(int i = 0;i<arr.size();i++){
    int j = i-1;
    while(j >= 0){ // 找所有坐标比它小的
    	while(j >= 0 && arr[j] >= arr[i])j--; // 忽略掉 大于等于 当前值的    
        if(prei[i] == -1 || len[prei[i]] <= len[j] ){ // 没找到时，或上次的长度更短
            prei[i] = j; // 建立链表 指向一个比它小的位置
            len[i] = len[j] + 1; // 记录长度
        }
        j--;
    }
}

字典序控制

上面的做法，满足了最长上升子序列，但是没有满足字典序最小，因为更新仅根据比当前值小和长度，来进行更新的。

例如1 3 2 4,会让4指向3而不是指向2

注意到，如果长度更短，那么相当于没有意义，因为长度的优先级大于字典序，所以只用考虑同长度情况下字典序的选取。

做到每一长度都记录的是到此字典序最小的值

注意到如果i<j，而到i和到j的长度相等，那么必有arr[i] >= arr[j]，否则j能有更大长度

因此，长度相等的情况，j一定字典序不大于i的字典序

for(int i = 0;i<arr.size();i++){
    int j = i-1;
    while(j >= 0){ // 找所有坐标比它小的
    	while(j >= 0 && arr[j] >= arr[i])j--; // 忽略掉 大于等于 当前值的    
        if(prei[i] == -1 || len[prei[i]] < len[j] ){ // 没找到时，或上次的长度更短
            prei[i] = j; // 建立链表 指向一个比它小的位置
            len[i] = len[j] + 1; // 记录长度
        }else if(len[prei[i]] == len[j])( // 长度相等的情况，一定`j`越大,字典序越小
            // 不更新
        )
        j--;
    }
}

效率优化

至此，从逻辑上已经满足题目要求的，最长上升子序列中最小字典序，但因为数据范围n <= 200000,上述算法复杂度$O(n^2)O(n^2)$, 一定会超时

所以考虑优化时间复杂度

对于数组来说一定会遍历一遍，所以外层的n次复杂度无法优化，考虑内层的n

内层的操作实际上是，找比当前位置值小，上升子序列最长的，最右测的位置

考虑用辅助数组 len2i[i],来记录当前长度为i的，最右侧的位置，这样内层效率变为了每次搜索时最长序列的长度，依然是$O(n^2)O(n^2)$

注意到随着，辅助数组下标增加arr[len2i[i]] 也是单调递增的，因此可以使用二分搜索。

为了方便使用内置的lower_bound进行二分搜索，增加len2v[i]=arr[len2i[i]] 来记录值。

也就有每次辅助数组中替换的位置查找，变成了二分，即

idx = lower_bound(len2v.begin(),len2v.end(),v) - len2v.begin();

题解

所以整合上面的内容

class Solution {
public:
    /**
     * retrun the longest increasing subsequence
     * @param arr int整型vector the array
     * @return int整型vector
     */
    vector<int> LIS(vector<int>& arr) {
        // write code here
        vector<int> len2v; // 记录值
        vector<int> len2i; // 记录下标
        vector<int> prei(arr.size(),-1); // 每个下标最长上升的上一个坐标
        for(int i = 0;i< arr.size();i++){
            int v = arr[i];
            if(len2v.size() == 0 || v > len2v.back()){ // 大于现有所有
                prei[i] = len2i.size() == 0? -1:len2i.back();
                len2v.push_back(v);
                len2i.push_back(i);
            }else{ // 小于等于当前最大值
                // p = first pos >= v
                int p = lower_bound(len2v.begin(),len2v.end(),v)  
                    - len2v.begin(); // 二分找 一个大于等于v的值
                prei[i] = p == 0? -1:len2i[p-1];
                len2v[p] = v;
                len2i[p] = i;
            }
        }
        int n = len2v.size(); // 最大长度
        vector<int> ans(n,0);
        int curi = len2i[n-1]; // 最大长度的最后一个值的坐标
        for(int i = 0;i < n;i++){
            ans[n-1-i] = arr[curi];
            curi = prei[curi]; // 上一个值的坐标
        }
        return ans;
    }
};

复杂度分析

时间复杂度: 先遍历数组，每次遍历最坏是二分查找下标，所以总时间复杂度为$O(n\cdot log(n))O(n\; \backslash cdot\; log(n))$

空间复杂度: 用来辅助记录值，下标，和上一个下标的都和数组长度相关，所以空间复杂度为$O(n)O(n)$