难 · 动态规划

最长上升子序列

子序列可以跳过元素但不能改变顺序 —— 在 10 9 2 5 3 7 里，2 3 7 合法，3 2 不合法。把 best[i] 定义成「恰好以位置 i 结尾的最长上升链」，每个元素只需问：在我之前谁比我小，他们的链有多长？

一句话答案对所有 j &lt; i 且 <code>a[j] &lt; a[i]</code> 取 <code>best[i] = 1 + max(best[j])</code>（没有则 1）；答案是所有 i 的最大值 —— O(n²) 双重循环。

题目

输入: 第一行是 n（1 ≤ n ≤ 500）。第二行 n 个整数（−1000 到 1000）。

输出: 最长严格上升子序列的长度。

样例:

输入输出
8
10 9 2 5 3 7 101 18		4
4
2 2 2 2		1

第一个样例的答案 4 是链 2、3、7、18（或 2、5、7、18）。第二个样例是严格性探测器：相等的邻居不能相连，所以四个 2 的长度是 1 而不是 4。

你的解答

main.cpp — 你的解答
「运行我的输入」用的自定义输入

判题在浏览器本地运行。死循环会在 3 秒后被自动中断 —— 但还是确保每个循环都有出口。代码随打随存。

卡住了？提示

提示 1 — 钉住结尾位置

「最长上升子序列」在你钉住它结尾之前是滑的。best[i] = 恰好以 i 结尾的最长链，把模糊目标变成 n 个精确子问题 —— 真答案就是其中最大者。这个「以这里结尾」的招数和 最大子段和 用的是同一个。

提示 2 — 每个元素从 1 起步

任何比较之前，best[i] = 1：单独一个元素就是长度为 1 的链。然后用最好的更小前驱去改进它。两个经典 bug 都坏在这条边界：忘了设（读到未初始化的全局数组 —— 本引擎不清零），或者把 best[i] 起步设成 0，导致链永远不算上自己的最后一个元素。

提示 3 — 严格就是严格

比较是 a[j] < a[i]，不是 <=。一旦允许相等邻居，全相等测试会返回 n 而不是 1 —— 判题的第二个样例就是专为这一个字符准备的。

题解（先自己试试！） 
#include <iostream>
using namespace std;

int a[505], best[505];

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

    int ans = 0;
    for (int i = 0; i < n; i++) {
        best[i] = 1;
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i] && best[j] + 1 > best[i]) {
                best[i] = best[j] + 1;
            }
        }
        if (best[i] > ans) ans = best[i];
    }

    cout << ans << endl;
    return 0;
}

O(n²) 双重循环是诚实版本；存在 O(n log n) 升级版 —— 为每个链长保存「最小可行尾元素」，插入新元素需要 二分查找。两者之间注意不变的东西：best[i] 的定义。更好的算法很少取代 DP 的含义；它们只是让同一个含义查得更快。

深度解析

为什么这样做对

钉住结尾:best[i] = 恰好以 i 结尾的最长严格上升链。于是每个 i 扫描自己的全部过去,找更小元素里链最长的那个 —— 每个至多 O(n) 个前驱,总共 O(n²) —— 全局答案就是所有结尾的最大值。「以这里结尾」的框定让模糊目标变得可算。

代价

时间 O(n²),空间 O(n) —— 500² = 二十五万次比较,瞬间完成。O(n log n) 升级版为每个链长保存最小可行尾元素、用二分插入,但 DP 定义原封不动。

常见错法

  • 把 a[j] <= a[i] 写成允许相等:全相等测试会返回 n 而不是 1 —— 一个字符,一个错答。
  • 扫描前忘了 best[i] = 1:本引擎里全局是垃圾值;即便在真编译器上,这条边界也是「链可以从任何地方开始」的根据。
  • 报告 best[n-1] 而不是所有 i 的最大值:最长链可能结束在任何位置(看那个递减测试 —— 它结束在位置 0)。

下一步

同一招「以这里结尾」的一维无对版本:最大子段和。提速升级需要 二分查找 来安放链尾。

记住这两句

  • best[i] = 1 + 更小前驱里最好的;答案 = 各结尾取最大。
  • 严格 < 和 <= 之差,就是「互不相同」和「非降序」之差。
🐞 这段是错的 —— 点开,亲手让它挂一次

用了 a[j] <= a[i] —— 相等邻居也能连,全 2 会给出 4 而不是 1

#include <iostream>
using namespace std;

int a[505], best[505];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    int ans = 0;
    for (int i = 0; i < n; i++) {
        best[i] = 1;
        for (int j = 0; j < i; j++) {
            if (a[j] <= a[i] && best[j] + 1 > best[i]) {   // bug: not strict
                best[i] = best[j] + 1;
            }
        }
        if (best[i] > ans) ans = best[i];
    }
    cout << ans << endl;
    return 0;
}