一本通 1285：最大上升子序列和

我是传送门

【题目描述】

一个数的序列(bi)，当(b_1<b_2<...<b_S)的时候，我们称这个序列是上升的。对于给定的一个序列((a1,a2,...,aN))，我们可以得到一些上升的子序列((a_{i1},a_{i2},a_{iK}))，这里(1≤i_1<i_2<...<i_K≤N)。比如，对于序列((1,7,3,5,9,4,8))，有它的一些上升子序列，如((1,7)),((3,8))等等。这些子序列中和最大为(18)，为子序列((1,9))的和。

你的任务，就是对于给定的序列，求出最大上升子序列和。注意，最长的上升子序列的和不一定是最大的，比如序列((100,1,2,3))的最大上升子序列和为(100)，而最长上升子序列为((1,3))。

【输入】

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

【输出】

最大上升子序列和。

【输入样例】

7

1 7 3 5 9 4 8

【输出样例】

18

【思路】

相信大家做到这个题目的时候，已经做过最长上升子序列了（不然你动规可能是倒着学的），在这里的话.....默认你已经会了那道题，那么我们就开始看这道题

这道题的题意就是：在要求是上升序列的前提下，输出最大值

其实这道题也和那一道题类似，直接把以前写的最长上升子序列的程序拿过来，将储存最长序列的值改为最大值就行了。

状态转移方程：(f[i]=max(f[i],f[j]+a[i]);)

下面看代码

【代码】

#include<bits/stdc++.h>
#define N 1010
#define INF 0x7f
using namespace std;

int a[N],f[N];
int n;

int main() {
    scanf("%d",&n);
    for(int i=1; i<=n; i++) {
        scanf("%d",&a[i]);
    }
    int maxn=-INF;
    for(int i=1; i<=n; i++) {
        f[i]=a[i];
        for(int j=1; j<i; j++) {
            if(a[j]<a[i]&&f[j]+a[i]>f[i]) {
                f[i]=f[j]+a[i];
            }
            maxn=max(maxn,f[i]);
        }
    }
    cout<<maxn<<'n';
    return 0;
}