题解 | 最大上升子序列和

#include <bits/stdc++.h>
using namespace std;

const int SIZE=100000;

int dp[SIZE];

int main(){
    int n;
    while(cin>>n){
        memset(dp,INT_MIN,sizeof(dp));
        int a[n];
        for(int i=0;i<n;i++){
            cin>>a[i];
        }
        int ans=0;
        for(int i=0;i<n;i++){
            dp[i]=a[i];
            for(int j=0;j<i;j++){
                if(a[j]<a[i])dp[i]=max(dp[i],dp[j]+a[i]);
            }
            ans=max(ans,dp[i]);
        }
        cout<<ans<<endl;
    }
}

相较于上一题，这题是上升，上题题解是下降，核心要求最大的和，而非长度，那么我们就求和即可往左扫描下降的例子，取等号也可以，逻辑上和上一个题解一样，只要从左到右依次生成，就可以根据前者的最大数值长度，根据条件的判断，不断生成出来新的数值，也就是上述的状态变化方程。#大学最后一个寒假，我想……#