动态规划解法

直接上代码：

#include<bits/stdc++.h> 
using namespace std;
int n,ans;               // n:序列长度,ans:最终最大上升子序列和
int a[1005],dp[1005];    // a:原始序列,dp[i]:以i结尾的最大上升子序列和
int main(){ 
    cin>>n;             // 输入序列长度
    for(int i=1;i<=n;i++){ 
        cin>>a[i];      // 输入每个元素
        dp[i]=a[i];     // 初始化dp[i]为只包含a[i]自身的和
    }
    // 动态规划计算所有以i结尾的上升子序列的最大和
    for(int i=1;i<=n;i++){ 
        for(int j=1;j<i;j++){   // 遍历i之前的所有元素
            if(a[i]>a[j]){          // 满足上升条件，可以接在j后面
                dp[i]=max(dp[i],a[i]+dp[j]); // 更新dp[i]
            }
        }
        ans=max(ans,dp[i]);        // 更新全局最大值
    }
    cout<<ans<<"\n";              // 输出结果
    return 0;
}