最大上升子序列和

最大上升子序列和

题目描述

一个数的序列$b_i$，当$b_1<b_2<...<b_S$的时候，我们称这个序列是上升的。

对于给定的一个序列($a_1,a_2,...,a_N$)，我们可以得到一些上升的子序列($a_{i_1}, a_{i_2}, ..., a_{i_K}$)，这里$1\leq i_1<i_2<...<i_K\leq N$。

比如，对于序列($1,7,3,5,9,4,8$)，有它的一些上升子序列，如($1,7$), ($3,4,8$)等等。

这些子序列中和最大为$18$，为子序列($1,3,5,9$)的和。

你的任务，就是对于给定的序列，求出最大上升子序列和。

注意，最长的上升子序列的和不一定是最大的，比如序列 ($100,1,2,3$) 的最大上升子序列和为 $100$，而最长上升子序列为($1,2,3$)。

输入格式

输入的第一行是序列的长度$N$ ($1\leq N\leq 1000$) 。第二行给出序列中的 $N$ 个整数，这些整数的取值范围都在 $0\sim10000$ (可能重复)。

输出格式

最大上升子序列和。

输入样例

7
1 7 3 5 9 4 8

输出样例

18

思路

令 $dp_i$ 为所有以 $v_i$ 结尾的上升子序列和的最大值。

则他的最大值可以有他前面的数推导而来：

如果前面没有数，那么就是 $v_i$

如果选择第一个数，那么就是 $dp_1 + v_i$

如果选择第二个数，那么就是 $dp_2 + v_i$

$\vdots$

如果选择第 $i-1$ 个数，那么就是 $dp_{i-1} + v_i$

转移方程 $dp_i = \mathop{max}\limits_{j\in[1,i-1]}\{dp_i,\ dp_j+v_i\}$

注意：$dp_i$ 应初始化为 $v_i$

CODE

void solve()
{
    int n, ans = 0;  cin >> n;
    vector<int> v(n), dp(n);
    for (auto &x : v)   cin >> x;
    for (int i=0;i<n;i++)
    {
        dp[i] = v[i];
        for (int j=0;j<i;j++)
            if (v[i] > v[j])
                dp[i] = max(dp[i], dp[j] + v[i]);
        ans = max(ans, dp[i]);
    }
    cout << ans;
}