文字教学

这道题用O(n²)的动态规划解决，核心思路是：

1. 定义状态：用 dp[i] 表示以第 i 个元素结尾的最长上升子序列的长度。
2. 初始化：每个 dp[i] 至少为1（元素本身就是一个子序列）。
3. 状态转移：对每个 i，遍历前面所有 j < i 的元素，若 a[j] < a[i]，则 dp[i] = max(dp[i], dp[j] + 1)。
4. 结果：所有 dp[i] 中的最大值就是最长上升子序列的长度。

代码

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

const int N = 5010;
int a[N], dp[N];

int main() {
    int n, i, j, ans = 0;
    cin >> n;
    for (i = 0; i < n; ++i) {
        cin >> a[i];
        dp[i] = 1;
    }
    for (i = 0; i < n; ++i) {
        for (j = 0; j < i; ++j) {
            if (a[j] < a[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        ans = max(ans, dp[i]);
    }
    cout << ans << endl;
    return 0;
}