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

题目链接

题目描述

给定一个由 $n$ 个正整数组成的数组 $a$ 。请你计算该数组的最长不下降子序列（Longest Non-decreasing Subsequence，简称 LNDS）的长度。对于一条子序列，要求保留原数组中的相对顺序，并满足子序列中的元素依次不小于前一个元素。

解题思路

本题要求解最长不下降子序列（LNDS）的长度。这是一个经典的动态规划问题，可以使用贪心算法结合二分查找进行优化，将时间复杂度降至 $\mathcal{O}(n \cdot \log n)$ 。

我们维护一个数组 $d$ ，其中 $d[k]$ 表示长度为 $k+1$ 的所有不下降子序列中，结尾元素的最小值。显然，数组 $d$ 是单调不降的。

我们遍历输入的数组 $a$ 中的每一个元素 $x$ ：

如果 $x$ 大于或等于 $d$ 数组的最后一个元素，说明 $x$ 可以接在目前最长的不下降子序列后面，形成一个更长的新序列。于是，我们将 $x$ 直接添加到 $d$ 数组的末尾。
如果 $x$ 小于 $d$ 数组的最后一个元素，我们就在 $d$ 数组中查找第一个严格大于 $x$ 的元素，并用 $x$ 替换它。这样做是因为，我们找到了一个长度与被替换元素所在位置对应的子序列，但其结尾更小（为 $x$ ）。这个更小的结尾为后续元素提供了更多成为不下降子序列一部分的可能性。

由于数组 $d$ 始终保持单调不降，上述查找过程可以使用二分查找来完成。遍历完整个输入数组 $a$ 后， $d$ 数组的长度就是原数组最长不下降子序列的长度。

代码

c++
java
python

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

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    if (n == 0) {
        cout << 0 << "\n";
        return 0;
    }

    vector<int> d;
    d.push_back(a[0]);

    for (int i = 1; i < n; i++) {
        if (a[i] >= d.back()) {
            d.push_back(a[i]);
        } else {
            // 找到 d 中第一个大于 a[i] 的元素并替换
            *upper_bound(d.begin(), d.end(), a[i]) = a[i];
        }
    }

    cout << d.size() << "\n";

    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();
        if (n == 0) {
            System.out.println(0);
            return;
        }
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        ArrayList<Integer> d = new ArrayList<>();
        d.add(a[0]);

        for (int i = 1; i < n; i++) {
            if (a[i] >= d.get(d.size() - 1)) {
                d.add(a[i]);
            } else {
                // 找到 d 中第一个大于 a[i] 的元素的位置
                int pos = upperBound(d, a[i]);
                d.set(pos, a[i]);
            }
        }

        System.out.println(d.size());
    }

    // 手动实现二分查找 upper_bound
    private static int upperBound(ArrayList<Integer> arr, int key) {
        int low = 0;
        int high = arr.size();
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (arr.get(mid) > key) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }
}

import bisect

n = int(input())
if n == 0:
    print(0)
else:
    a = list(map(int, input().split()))
    
    d = [a[0]]
    
    for i in range(1, n):
        if a[i] >= d[-1]:
            d.append(a[i])
        else:
            # 找到 d 中第一个大于 a[i] 的元素的位置并替换
            pos = bisect.bisect_right(d, a[i])
            d[pos] = a[i]
            
    print(len(d))

算法及复杂度

算法：贪心 + 二分查找
时间复杂度： $\mathcal{O}(n \cdot \log n)$ ，其中 $n$ 是数组的长度。遍历数组需要 $\mathcal{O}(n)$ ，每次二分查找需要 $\mathcal{O}(\log n)$ 。
空间复杂度： $\mathcal{O}(n)$ ，用于存储辅助数组 $d$ 。