题解 | #最长不下降子序列#

题目链接

最长不下降子序列

题目描述

给定一个由 $n$ 个正整数组成的数组 $a$ 。请你计算该数组的最长不下降子序列（Longest Non-decreasing Subsequence, LNDS）的长度。

子序列是在不改变剩余元素相对顺序的情况下，从原数组中删除任意数量元素得到的新数组。不下降子序列是指子序列中的每个元素都大于或等于它的前一个元素。

输入:

第一行一个整数 $n$ ，表示数组的元素数量。
第二行 $n$ 个整数，代表数组元素。

输出:

一个整数，表示最长不下降子序列的长度。

解题思路

这是一个非常经典的动态规划问题。一个朴素的 $\mathcal{O}(n^2)$ 解法是定义 $dp[i]$ 为以 $a[i]$ 结尾的最长不下降子序列的长度，但这对于 $n$ 达到 $10^5$ 的数据规模来说太慢了。因此，我们需要一个更高效的 $\mathcal{O}(n \log n)$ 算法。

这种高效算法的核心思想是维护一个辅助数组，我们称之为 d。这个数组 d 的性质是：d[k] 存储的是所有长度为 k+1 的不下降子序列中，结尾元素的最小值。这个 d 数组在算法执行过程中，将始终保持不下降的顺序。

算法流程如下：

初始化一个空的数组 d。
遍历输入数组 a 中的每一个元素 num。
对于每个 num，我们在 d 数组中进行二分查找，目的是找到第一个严格大于 num 的元素的位置。
- 情况一: 如果在 d 中找到了这样一个元素（假设在索引 j），我们就用 num 替换掉 d[j]。这一步的意义在于：我们找到了一个长度为 j+1 的新的不下降子序列，它的结尾元素是 num。由于 num 小于原来的 d[j]，这个新的子序列对于后续的元素来说，有更大的潜力去扩展，因为它降低了“接龙”的门槛。
- 情况二: 如果在 d 中找不到严格大于 num 的元素，这意味着 num 大于或等于 d 中的所有元素。因此，num 可以接在 d 中最长的那个子序列后面，形成一个更长的不下降子序列。我们直接将 num 添加到 d 数组的末尾。
遍历完整个输入数组 a 后，d 数组的长度就是原数组的最长不下降子序列的长度。

这个算法的关键在于，我们并不关心 d 数组中的具体元素是什么（d 数组本身并非一个LNDS），我们只关心它的长度，因为它正确地记录了在遍历过程中所能达到的最长不下降子序列的长度。

二分查找“第一个严格大于某值的元素”，在C++中可以直接用 std::upper_bound 实现，在Python中用 bisect.bisect_right 实现。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> d;
    for (int i = 0; i < n; ++i) {
        int num;
        cin >> num;
        // 查找 d 中第一个严格大于 num 的元素
        auto it = upper_bound(d.begin(), d.end(), num);
        if (it == d.end()) {
            // 如果没找到，说明 num 可以扩展最长的子序列
            d.push_back(num);
        } else {
            // 否则，用 num 替换那个元素，以获得更优的子序列
            *it = num;
        }
    }
    cout << d.size() << endl;
    return 0;
}

import java.util.Scanner;
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        ArrayList<Integer> d = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            int num = sc.nextInt();
            int pos = upperBound(d, num);
            if (pos == d.size()) {
                d.add(num);
            } else {
                d.set(pos, num);
            }
        }
        System.out.println(d.size());
    }

    // 手动实现 upper_bound，查找第一个严格大于 target 的元素的位置
    private static int upperBound(ArrayList<Integer> list, int target) {
        int left = 0, right = list.size();
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (list.get(mid) <= target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}

import bisect

n = int(input())
a = list(map(int, input().split()))
d = []

for num in a:
    # 查找 d 中第一个严格大于 num 的元素的位置
    pos = bisect.bisect_right(d, num)
    if pos == len(d):
        # 如果没找到，说明 num 可以扩展最长的子序列
        d.append(num)
    else:
        # 否则，用 num 替换那个元素，以获得更优的子序列
        d[pos] = num

print(len(d))

算法及复杂度

算法：动态规划 + 二分查找
时间复杂度： $\mathcal{O}(n \log n)$ - 我们遍历输入数组 $n$ 次，每次在辅助数组 d 中进行一次二分查找。d 的长度最多为 $n$ ，因此二分查找的时间复杂度为 $\mathcal{O}(\log n)$ 。
空间复杂度： $\mathcal{O}(n)$ - 辅助数组 d 在最坏情况下（例如输入数组本身就是不下降的）长度会增长到 $n$ 。