最长递增子序列

题意

求数组的最长严格递增子序列长度。

思路

维护 tails 数组：tails[k] 表示长度为 k+1 的递增子序列的最小结尾元素。对每个 x，用 lower_bound 找到 tails 中第一个 $\geqslant x$ 的位置并替换；若 x 大于所有 tails，则追加。

严格递增用 lower_bound（ $\geqslant$ ），非严格递增用 upper_bound（ $>$ ）。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int lengthOfLIS(vector<int> &nums) {
        vector<int> tails;
        for (int x : nums) {
            auto it = lower_bound(tails.begin(), tails.end(), x);
            if (it == tails.end())
                tails.push_back(x);
            else
                *it = x;
        }
        return tails.size();
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n);
    for (int &x : a)
        cin >> x;
    cout << Solution().lengthOfLIS(a) << '\n';
    return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25#!/usr/bin/env python3
import bisect
from typing import List


class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        tails = []
        for x in nums:
            i = bisect.bisect_left(tails, x)
            if i == len(tails):
                tails.append(x)
            else:
                tails[i] = x
        return len(tails)


def main():
    n = int(input())
    a = list(map(int, input().split()))
    print(Solution().lengthOfLIS(a))


if __name__ == "__main__":
    main()

复杂度

时间复杂度： $O(n \log n)$ 。
空间复杂度： $O(n)$ 。

总结

LIS 的 $O(n \log n)$ 解法：tails 数组维护的是"各长度最优结尾"，lower_bound 更新保证严格递增。tails 的长度即为答案，但 tails 本身不一定是合法的子序列。

目录

题意

思路

代码

复杂度

总结