$\LARGE\color{orange}{刷题日记(算法提高课)}$

本题就是基本的 LIS ，把定义改一下就可以

$f[i]$ 所表示的集合为以 $a[i]$ 为结尾的上升子序列，$f[i]$ 所表示的值为所有子序列当中和的最大值

状态转移方程为：$f[i]\ =\ max(f[i],\ f[j]\ +\ a[i])$ ，最后取 $f[i]$ 的最大值即可

完整代码：

#include <iostream>

using namespace std;

const int N = 1010;
int a[N], f[N];
int n;

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    for(int i = 1; i <= n; i++)
    {
        f[i] = a[i];
        for(int j = 1; j < i; j++)
            if(a[j] < a[i]) f[i] = max(f[i], f[j] + a[i]);
    }
    int ans = 0;
    for(int i = 1; i <= n; i++) ans = max(ans, f[i]);
    cout << ans << endl;
    return 0;
}