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

#include <iostream>
using namespace std;
const int maxn=1000;
int a[maxn];
int dp[maxn];
void init(){
    for(int i=0;i<maxn;i++){
        a[i]=0;
        dp[i]=0;
    }
}
int main() {
    int n;
    while(cin>>n){
        for(int i=0;i<n;i++) {
            cin>>a[i];
            dp[i]=a[i];
            }
        int MAX=0;
        for(int i=0;i<n;i++){
            if(i==0) continue;
            else{
                for(int j=0;j<i;j++){
                    if(a[j]<a[i]) dp[i]=max(dp[i],dp[j]+a[i]);
                }
            }
            MAX=max(MAX,dp[i]);
        }
        cout<<MAX<<endl;

    }
}