板子题

/*
 * @Author: YMYS
 * @Date: 2024-12-17 08:44:40
 * @LastEditTime: 2024-12-19 09:57:52
 * @FilePath: \VScode-C&C++-Coding\Acwing\算法提高课\1.动态规划\2.最长上升子序列模型\5.最大上升子序列和.cpp
 * @URL:https://www.acwing.com/problem/content/1018/
 * @Description: 1016. 最大上升子序列和
 * 
 * 思路：把数组的性质换了而已，牢记模板的基础代码即可
 */
#include<bits/stdc++.h>

#define int long long

using namespace std;

typedef long long ll;

const int N = 1010;

int n;
int w[N],f[N],sum[N];

signed main()
{
#ifdef ABC
    freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\in.in", "r", stdin);
    freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\out.out", "w", stdout);
#endif
    cin>>n;
    for(int i=1;i<=n;i++) cin>>w[i];

    for(int i=1;i<=n;i++){
        // f[i] = 1;//初始值只有起始点一个数，所以长度为1
        sum[i] = w[i];//初始值为只有起始点一个数的值
        for(int j =1;j<i;j++){
            if(w[i]>w[j]){
                // f[i] = max(f[i], f[j]+1);//这个在记录最长上升子序列的长度
                sum[i] = max(sum[i], sum[j]+w[i]);//这个在记录最大上升子序列的和
            }
        }
    }

    int res = 1;
    for(int i =1;i<=n;i++){
        res = max(res, sum[i]);
    }

    cout<<res<<endl;

    return 0;
}