最长上升(递增)子序列

September 28, 2020

题目

给定一个整数数组，求其单调递增的子序列(subsequence)的最大长度。

思路

此处子序列可理解为逻辑上从原数组筛出任意个元素并按照其在原数组中的出现顺序排列而成的新数组，注意其与字串(substring)概念不同。若采用枚举方法，子序列的个数随输入数组元素个数呈指数增长，无法暴力枚举解题。

此处考虑使用动态规划(DP)方法，参考 DPV算法书及相应教学视频，将元素间的小于关系以有向边的形式给出，该问题转化为求对应有向无环图(DAG)的直径(diameter, 即最长路径长度)。

我们只需要维护一个初始为空的递增数组，从头到尾遍历输入数组的元素，当递增数组为空或新元素大于其尾部元素时，直接将其压入递增数组，否则寻找递增数组中不小于该元素的最小元素并进行替换。最后输出递增数组长度即可。整体时间复杂度 O(nlog(n))，分别对应于线性遍历的步数和二分查找的耗时。

该方法的本质是记录当前所有长度为 k 的递增子序列中的最大元素的最小值(即构成 k+1 长度递增子序列的最低门槛)，该值即我们所维护的递增数组的第 k 个元素。基于该信息继续采用贪心策略，对每个新遇到的元素尝试构造以其为最大元素的最长递增子序列(即寻找首个小于自己的“长度为 k 的递增子序列中的最大元素的最小值”对应的 k)，并更新长度为 k+1 的递增子序列中的最大元素的最小值。(hhhhh，好拗口，下次试试能不能插入数学公式)。

代码

建议使用微信电脑客户端阅读:

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        // hinted by 6515 course textbook
        // its actually finding dag's diameter
        std::vector<int> rank2max;
        
        for (auto num:nums) {
            if (rank2max.empty() || num > rank2max.back()) {
                rank2max.push_back(num);
            } else {
                auto it = std::upper_bound(rank2max.begin(), rank2max.end(), num-1);
                *it = num;
            }
        }
        
        return rank2max.size();
    }
};

练习

编程题:

LeetCode #300

代码阅读题:

读写能力一手抓:) 这里给一个稍进阶的版本, 要求计算给定数组中前半段为单调递减子序列后半段为单调递增子序列，两子序列长度相同且最小元素相同的子序列的最大长度。(吃葡萄不吐葡萄皮hhhh，读懂就好, 记得登电脑端来看代码)

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
/*
testcase:
3
9
5 4 3 2 1 2 3 4 5
5
1 2 3 4 5
14
87 70 17 12 14 86 61 51 12 90 69 89 4 65

8
0
6
*/

void gen_LDC(std::vector<int> &arr, std::vector<int> &LDC, int arr_size) {
    std::vector<int> rank2max4LDC;
    for (int i = 0; i < arr_size; i++) {
        int num = arr[i];

        if (rank2max4LDC.empty() || rank2max4LDC.back() > num) {
            rank2max4LDC.push_back(num);
            LDC[i] = rank2max4LDC.size();
        } else {
            auto it = std::upper_bound(rank2max4LDC.begin(), rank2max4LDC.end(), num+1,
                                        [](const int a, const int b) {return a > b;});
            *it = num;
            LDC[i] = it - rank2max4LDC.begin() + 1;
        }
    }
}

int main() {
    int testcase_num;
    std::cin >> testcase_num;
    while (testcase_num-- > 0) {
        int arr_size;
        std::cin >> arr_size;
        std::vector<int> arr(arr_size);
        std::vector<int> LIC(arr_size, 0);
        std::vector<int> LDC(arr_size, 0);
        for (int i = 0; i < arr_size; i++) {
            std::cin >> arr[i];
        }
        // firstly construct LDC&LIC by DP
        gen_LDC(arr, LDC, arr_size);
        std::reverse(arr.begin(), arr.end());
        gen_LDC(arr, LIC, arr_size);
        std::reverse(arr.begin(), arr.end());
        std::reverse(LIC.begin(), LIC.end());

        // then argsort arr, for each equal region, calc max len.
        std::vector<std::pair<int, int> > val2idx;
        for (int i = 0; i < arr_size; i++) {
            val2idx.push_back(std::make_pair(arr[i], i));
        }
        std::sort(val2idx.begin(), val2idx.end());
        int max_len = 0; // start gen result, use stacks to turn O(N^2) to O(N)
        std::stack<int> LIC_maxlen_on_right; // LDC_maxlen_on_left is useless

        for (int i = 0; i < arr_size - 1;) {
            int j, k;
            for (j = i + 1; j < arr_size; j++) {
                if (val2idx[i].first != val2idx[j].first) { // forget .first
                    j--;
                    break;
                }
            }
            if (j == arr_size) j--;

            k = j;
            if (k > i) {
                LIC_maxlen_on_right.push(LIC[val2idx[k].second]);
                k--;
            }
            while (k > i) {
                int current_max = LIC_maxlen_on_right.top();
                int new_LIC_len = LIC[val2idx[k].second];
                LIC_maxlen_on_right.push(std::max(current_max, new_LIC_len));
                k--;
            }

            int current_max_LDC = LDC[val2idx[i].second];
            for (k = i; k < j; k++) {
                current_max_LDC = std::max(current_max_LDC, LDC[val2idx[k].second]);
                int concat_len = 2 * std::min(current_max_LDC, LIC_maxlen_on_right.top());
                max_len = std::max(max_len, concat_len);
                LIC_maxlen_on_right.pop();
            }
            i = j + 1;
            // LIC_maxlen_on_right.clear // should already be empty
        }

        std::cout << max_len << std::endl;
    }
    return 0;
}

秘籍

继续推荐邓公的数据结构与算法 MOOC 大讲堂👍 数据结构(上), 数据结构(下), THUOJ, DSA.WORKSPACE，十二道编程题做了不吃亏，做了不上当(就是不能用 STL 各种结构全要手动实现 hhhh)