关于递增数列问题，如何使用动态规划思想解决。

Question

关于递增数列问题，如何使用动态规划思想解决。
从数列中选出若干个数字（至少选择一个），这些数字相对顺序与他们对应在数列中的相对顺序一致， 同时要求其大小单调递增，求满足条件的这些数字的最大和。

第一行输入 1 个整数N，表示数列大小。（1≤N≤2000）
第二行输入 N 个整数 Ai，表示数列中的每个数字。（−10000≤Ai≤10000）。

一个整数，表示满足条件的这些数字的最大和。
样例输入：
5
1 3 1 5 -2
样例输出：
9

Answer 1

动态规划的基本思想是将原问题分解为若干个子问题，从而通过计算每个子问题的答案来解决原问题。在本题中，我们可以使用一个数组，记录以当前数字结尾的单调递增子数列的最大和。

我们令dp[i]表示以第i个数字结尾的单调递增子数列的最大和，那么，dp[i]可以由以下状态转移方程得到：

dp[i] = max(dp[j]) + a[i] (0 <= j < i and a[j] < a[i])

代码如下：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2010; // 定义数列的最大长度

int n; // 数列的长度
int a[N]; // 定义数列
int dp[N]; // 定义DP数组，dp[i]表示以第i个数字结尾的单调递增子数列的最大和

int main()
{
    cin >> n; // 输入数列的长度
    for (int i = 0; i < n; i ++) cin >> a[i]; // 输入数列中的数字
    for (int i = 0; i < n; i ++)
    {
        dp[i] = a[i]; // 初始化dp[i]，设为数列中的第i个数字
        for (int j = 0; j < i; j ++)
        {
            if (a[j] < a[i]) dp[i] = max(dp[i], dp[j] + a[i]); // 如果a[j] < a[i]，更新dp[i]的值
        }
    }
    int ans = 0; // 定义答案
    for (int i = 0; i < n; i ++) ans = max(ans, dp[i]); // 求出答案
    cout << ans << endl; // 输出答案
    return 0;
}