Solution

一道很明显的 DP 题。
和最长上升子序列有点像，只需要修改一部分。

思路：

• $dp_i$ 表示以元素 $i$ 结尾的最大上升子序列和；
• 每次循环都遍历前面的元素：
• • 如果可以加入这个序列，就更新答案。

接下来就没什么好说的了，上代码：

AC Code

#include <iostream>
#include <climits>
using namespace std;
const int N=1002;
int a[N];
int dp[N]; // dp[i] 表示以 i 结尾的最大上升子序列和
signed main(){
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int n; cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];

    int ans=INT_MIN; // INT_MIN 为 int 所能接受的最小值
    for(int i=1;i<=n;i++){
        dp[i] = a[i]; // 先假设以 i 结尾的最大和为 a[i]
        for(int j=1;j<=i-1;j++){ // 遍历前面的元素
            if(a[j] < a[i]){ // 如果可以加入这个序列
                dp[i] = max(dp[i], dp[j] + a[i]); // 更新 dp
                ans = max(ans, dp[i]); // 更新答案
            }
        }
    }

    cout<<ans;
    return 0;
}