P1309 最长单调递增子序列

这是一道经典的动态规划问题，可以使用 O(n^2) 的时间复杂度解决。具体的解题思路如下：

1. 定义一个数组 dp，其中 dp[i] 表示以第 i 个数为结尾的最长单调递增子序列的长度。

2. 初始时，所有的 dp[i] 都为 1，因为每个数本身就是一个长度为 1 的单调递增子序列。

3. 对于第 i 个数，遍历它之前的所有数 j，如果当前数 nums[i] 大于 nums[j]，则可以将第 j 个数加入到以第 i 个数为结尾的子序列中，此时 dp[i] 的值就可以更新为 dp[j]+1。

4. 最终的答案就是 dp 数组中的最大值。

代码实现如下：

int n;
int nums[MAXN], dp[MAXN];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> nums[i];
        dp[i] = 1;
    }

    int ans = 1;
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        ans = max(ans, dp[i]);
    }

    cout << ans << endl;

    return 0;
}