算法【最长递增子序列问题与扩展】

本文讲解最长递增子序列以及最长不下降子序列的最优解，以及一些扩展题目。本文中讲述的是最优解，时间复杂度是O(n*logn)，空间复杂度O(n)，好实现、理解难度不大。这个问题也可以用线段树来求解，时间和空间复杂度和本节讲的最优解没有区别。

下面通过一些题目来加深理解。

题目一

测试链接：https://leetcode.cn/problems/longest-increasing-subsequence/

分析：这道题的基本做法是非常简单和常见的，所以下面给出基本做法以及优化时间复杂度的做法。基本做法的时间复杂度是O(n²)。代码如下。

class Solution {
public:
    int dp[2500];
    int lengthOfLIS(vector<int>& nums) {
        int length = nums.size();
        int ans = 1;
        dp[0] = 1;
        for(int i = 1;i < length;++i){
            dp[i] = 1;
            for(int j = 0;j < i;++j){
                if(nums[i] > nums[j]){
                    dp[i] = dp[i] > dp[j] + 1 ? dp[i] : dp[j] + 1;
                }
            }
            ans = ans > dp[i] ? ans : dp[i];
        }
        return ans;
    }
};

优化时间复杂度之后，能做到O(n*logn)。通过一个end数组，end[i]表示长度为i+1的严格递增子序列的最小结尾，故可以知道end数组是有序的，对于有序数组的查找可以采用二分查找法，这也是优化时间复杂度所在。最后end数组的长度就是最长严格递增子序列的长度。代码如下。

class Solution {
public:
    int end[2500];
    int get_index(int len, int num){
        int ans = -1;
        int l = 0, r = len - 1, m;
        while (l <= r)
        {
            m = l + (r - l) / 2;
            if(end[m] >= num){
                ans = m;
                r = m - 1;
            }else{
                l = m + 1;
            }
        }
        return ans;
    }
    int lengthOfLIS(vector<int>& nums) {
        int length = nums.size();
        int len = 1, find;
        end[0] = nums[0];
        for(int i = 1;i < length;++i){
            find = get_index(len, nums[i]);
            if(find == -1){
                end[len++] = nums[i];
            }else{
                end[find] = nums[i];
            }
        }
        return len;
    }
};

题目二

测试链接：https://leetcode.cn/problems/russian-doll-envelopes/

分析：这道题的思路较为难想，其实只需要对于每个信封宽度从小到大排序，相同宽度的，对于高度从大到小排序，然后仅对高度求一个最长递增子序列即可。代码如下。

class Solution {
public:
    int end[100000];
    int get_index(int len, int num){
        int ans = -1;
        int l = 0, r = len - 1, m;
        while (l <= r)
        {
            m = l + (r - l) / 2;
            if(end[m] >= num){
                ans = m;
                r = m - 1;
            }else{
                l = m + 1;
            }
        }
        return ans;
    }
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        auto cmp = [](vector <int> v1, vector<int> v2){
            return v1[0] < v2[0] || (v1[0] == v2[0] && v1[1] > v2[1]);
        };
        sort(envelopes.begin(), envelopes.end(), cmp);
        int length = envelopes.size();
        int len = 1, find;
        end[0] = envelopes[0][1];
        for(int i = 1;i < length;++i){
            find = get_index(len, envelopes[i][1]);
            if(find == -1){
                end[len++] = envelopes[i][1];
            }else{
                end[find] = envelopes[i][1];
            }
        }
        return len;
    }
};

题目三

测试链接：https://leetcode.cn/problems/minimum-operations-to-make-the-array-k-increasing/

分析：这道题其实是将一个数组分为了k个子数组，然后只需要对每个子数组求一个最长不下降子序列，然后用子数组长度减去这个最长不下降子序列的长度就是需要操作的次数，将每一个子数组的操作次数求和即可得到答案。代码如下。

class Solution {
public:
    int nums[100000];
    int end[100000];
    int kIncreasing(vector<int>& arr, int k) {
        int length = arr.size();
        int ans = 0;
        int size;
        for(int i = 0;i < k;++i){
            size = 0;
            for(int j = i;j < length;j += k){
                nums[size++] = arr[j];
            }
            ans += (size - get_num(size));
        }
        return ans;
    }
    int get_num(int size){
        end[0] = nums[0];
        int len = 1;
        for(int i = 1, find;i < size;++i){
            find = get_index(nums[i], len);
            if(find == -1){
                end[len++] = nums[i];
            }else{
                end[find] = nums[i];
            }
        }
        return len;
    }
    int get_index(int num, int len){
        int ans = -1;
        int m;
        int l = 0;
        int r = len - 1;
        while (l <= r)
        {
            m = (l + r) / 2;
            if(end[m] > num){
                ans = m;
                r = m - 1;
            }else{
                l = m + 1;
            }
        }
        return ans;
    }
};

题目四

测试链接：https://leetcode.cn/problems/maximum-length-of-pair-chain/

分析：因为结果中后一个数对的第一个数一定会比前一个数对的第一个数大，所以我们先对第一个数从小到大排序。然后对于去end数组查找的数选用数对的第一个数，但对end数组进行赋值的时候我们选用数对的第二个数，这是因为题目要求后一个数对的第一个数必须比前一个数对的第二个数大。代码如下。

class Solution {
public:
    int end[1000];
    int findLongestChain(vector<vector<int>>& pairs) {
        sort(pairs.begin(), pairs.end(), [](vector<int> v1, vector<int> v2)->bool{
            return v1[0] < v2[0];
        });
        int length = pairs.size();
        end[0] = pairs[0][1];
        int len = 1;
        for(int i = 0, find;i < length;++i){
            find = get_index(len, pairs[i][0]);
            if(find == -1){
                end[len++] = pairs[i][1];
            }else{
                end[find] = end[find] > pairs[i][1] ? pairs[i][1] : end[find];
            }
        }
        return len;
    }
    int get_index(int len, int num){
        int ans = -1;
        int m, l = 0, r = len - 1;
        while (l <= r)
        {
            m = (l + r) / 2;
            if(end[m] >= num){
                ans = m;
                r = m - 1;
            }else{
                l = m + 1;
            }
        }
        return ans;
    }
};

这道题的最优解法是贪心。对于数对的第二个数从小到大排序，然后从一个开始寻找符合条件数对，遍历完即可得到答案。代码如下。

class Solution {
public:
    int findLongestChain(vector<vector<int>>& pairs) {
        sort(pairs.begin(), pairs.end(), [](vector<int> v1, vector<int> v2)->bool{
            return v1[1] < v2[1];
        });
        int pre = -2000;
        int ans = 0;
        int length = pairs.size();
        for(int i = 0;i < length;++i){
            if(pairs[i][0] > pre){
                pre = pairs[i][1];
                ++ans;
            }
        }
        return ans;
    }
};

题目五

测试链接：https://www.luogu.com.cn/problem/P8776

分析：这道题需要理解，被修改的数和被修改为的数紧靠在一起求得的答案和原题目没有区别。这样被修改的数和被修改为的数就组成了一个子数组。对子数组的左边，求得以子数组左边下标为结尾的最长不下降子序列的长度且这个最长不下降子序列的最大值不能超过这个被修改为的数；对于这个子数组的右边，求得以子数组右边为开头的最长不下降子序列的长度。将两个最长不下降子序列的长度相加再加上k就是这个子数组求得的答案，遍历数组即可得到最大值。代码如下。

#include <iostream>
using namespace std;
int N, K;
int arr[100000];
int Right[100000];
int End[100000];
int get_index1(int num, int len){
    int ans = -1;
    int m, l = 0, r = len - 1;
    while (l <= r)
    {
        m = (l + r) / 2;
        if(End[m] < num){
            ans = m;
            r = m - 1;
        }else{
            l = m + 1;
        }
    }
    return ans;
}
void get_right(){
    End[0] = arr[N-1];
    int len = 1;
    Right[N-1] = 1;
    for(int i = N-2, find;i >= K;--i){
        find = get_index1(arr[i], len);
        if(find == -1){
            End[len++] = arr[i];
            Right[i] = len;
        }else{
            End[find] = arr[i];
            Right[i] = find+1;
        }
    }
}
int get_index2(int num, int len){
    int ans = -1;
    int m, l = 0, r = len - 1;
    while (l <= r)
    {
        m = (l + r) / 2;
        if(End[m] > num){
            ans = m;
            r = m - 1;
        }else{
            l = m + 1;
        }
    }
    return ans;
}
int main(void){
    scanf("%d%d", &N, &K);
    for(int i = 0;i < N;++i){
        scanf("%d", &arr[i]);
    }
    get_right();
    int ans = K + Right[K];
    End[0] = arr[0];
    int len = 1;
    for(int i = K+1, find;i < N;++i){
        find = get_index2(arr[i], len);
        find = find == -1 ? len : find;
        ans = ans > (find + K + Right[i]) ? ans : (find + K + Right[i]);
        find = get_index2(arr[i-K], len);
        if(find == -1){
            End[len++] = arr[i-K];
        }else{
            End[find] = arr[i-K];
        }
    }
    printf("%d", ans);
}