题解 | #最大上升子序列和#

max(dp[i],max(dp[j]+num[i]|num[j]<num[i])

#include <iostream>
using namespace std;

//最大上升子序列和
int num[1010];
int dp[1010];

int maxincrease(int n){
    int ans=0;
    dp[0]=num[0];
    for(int i=1;i<n;i++){
        dp[i]=num[i];
        for(int j=0;j<i;j++){
            if(num[j]<num[i])
                dp[i]=max(dp[i],dp[j]+num[i]);
        }
    ans=max(ans,dp[i]);
    }
    return ans;
}

int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>num[i];
    }
    int ans=maxincrease(n);
    cout<<ans<<endl;
    return 0;
}