给定一个长度为 nnn 的数组 a1a_1a1​,a2a_2a2​,…,ana_nan​，问其中的和最大的上升子序列。也就是说，我们要找到数组 p1p_1p1​,p2p_2p2​,…,pmp_mpm​，满足 1≤p1

输入格式

第一行一个数字 nnn。

接下来一行 nnn 个整数 a1,a2,…,ana_1,a_2,…,a_na1​,a2​,…,an​。

输出格式

一个数，表示答案。

样例输入

6
3 7 4 2 6 8

样例输出

21

数据规模

所有数据保证 1≤n≤10001≤n≤10001≤n≤1000,1≤ai≤1051≤a_i≤10^51≤ai​≤105。

解题思路：

对于数列的动态规划问题，例如字符串序列、整数序列等

前缀的概念很重要，它就是动态规划中所谓的”最优子结构“

要知道以任意数字结尾的最大和上升子序列，只需要知道该数字能够接上的最大前缀是多少即可

举个例子来说，对于3 7 4 2 6 8，如果我们想知道以888结尾的最大和上升子序列，就需要找到888能够接上的最大前缀是多少

首先考虑有几种前缀：

（1）333：3

（2）7：3 7

（3）4：3 4

（4）222：2

（5）666：3 4 6

显然以666结尾是最大前缀，但是我们还需要考虑另外一个条件：”能够接上的“

需要符合的条件很简单，只需要检查结尾数字和888的大小关系即可

最后，AC代码如下

#include 
using namespace std;
const int max_n = 1000;
const int max_a = 1e5;int n;
int num_arr[max_n + 1];
int sum[max_n + 1];int main() {cin >> n;for (int i = 1; i <= n; i++) {cin >> num_arr[i];sum[i] = num_arr[i];}int ans = 0, pre = 0;for (int i = 1; i <= n; i++) {pre = 0;for (int j = 1; j <= i - 1; j++) {if (num_arr[j] < num_arr[i])pre = max(pre, sum[j]);}sum[i] += pre;ans = max(ans, sum[i]);}cout << ans << endl;return 0;
}