最长不下降子序列

思路

经典中的经典——最长不下降子序列（Longest Non-Decreasing Subsequence, LNDS）。

先搞清楚题意：从数组里挑出一些元素（保持原来的相对顺序），使得这些元素从左到右不递减（允许相等），问最多能挑多少个。

朴素 DP：

最直觉的做法： 表示以 结尾的最长不下降子序列长度。转移时枚举 ，如果 ，就可以接上去：

$$

但这是 的，数据量大了扛不住。

贪心 + 二分：

更聪明的做法是维护一个数组 tails，其中 tails[i] 表示长度为 的所有不下降子序列中，末尾元素的最小值。

这个数组有一个很好的性质：它是单调不递减的。

对于每个新元素 ：

  • 如果 tails 的最后一个元素，直接追加到末尾，子序列长度 +1
  • 否则，用二分查找找到 tails 中第一个严格大于 的位置，替换掉它

这里的关键点：因为我们要求的是不下降（允许相等），所以要找 upper_bound（第一个严格大于 的位置）。如果题目要求的是严格递增，那就该用 lower_bound（第一个大于等于 的位置）。

为什么替换是对的？因为替换后不影响已有的子序列长度，但让末尾变小了，后续更容易接上新元素，是一种贪心策略。

最终 tails 数组的长度就是答案。

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    vector<int> tails; // tails[i] = 长度为 i+1 的不下降子序列的最小末尾
    for (int i = 0; i < n; i++) {
        int x;
        scanf("%d", &x);
        // upper_bound: 找第一个严格大于 x 的位置（允许相等，所以不是 lower_bound）
        auto it = upper_bound(tails.begin(), tails.end(), x);
        if (it == tails.end()) {
            tails.push_back(x);
        } else {
            *it = x;
        }
    }
    printf("%d\n", (int)tails.size());
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        StringTokenizer st = new StringTokenizer(br.readLine().trim());

        int[] tails = new int[n];
        int len = 0;

        for (int i = 0; i < n; i++) {
            int x = Integer.parseInt(st.nextToken());
            // 手写二分找 upper_bound（第一个严格大于 x 的位置）
            int lo = 0, hi = len;
            while (lo < hi) {
                int mid = (lo + hi) >>> 1;
                if (tails[mid] > x) {
                    hi = mid;
                } else {
                    lo = mid + 1;
                }
            }
            tails[lo] = x;
            if (lo == len) len++;
        }

        System.out.println(len);
    }
}

import bisect, sys
input = sys.stdin.readline

def main():
    n = int(input())
    a = list(map(int, input().split()))
    tails = []
    for x in a:
        # bisect_right = upper_bound (for non-decreasing)
        pos = bisect.bisect_right(tails, x)
        if pos == len(tails):
            tails.append(x)
        else:
            tails[pos] = x
    print(len(tails))

main()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', l => lines.push(l));
rl.on('close', () => {
    const n = parseInt(lines[0]);
    const a = lines[1].split(' ').map(Number);
    const tails = [];
    for (let i = 0; i < n; i++) {
        const x = a[i];
        // upper_bound: first index where tails[idx] > x
        let lo = 0, hi = tails.length;
        while (lo < hi) {
            const mid = (lo + hi) >>> 1;
            if (tails[mid] > x) hi = mid;
            else lo = mid + 1;
        }
        if (lo === tails.length) tails.push(x);
        else tails[lo] = x;
    }
    console.log(tails.length);
});

复杂度

  • 时间复杂度：，每个元素做一次二分查找
  • 空间复杂度：，tails 数组最长为