题解 | 最大上升子序列和

#include <algorithm>
#include <iostream>
using namespace std;
const int N = 1005;
int dp[N],A[N];

int main() {
    int n;
    while (cin >> n) { // 注意 while 处理多个 case
        for(int i = 1;i<=n;i++)cin>>A[i];

        for(int i = 1;i<=n;i++){
            dp[i]=A[i];
            for(int j=1;j<i;j++){
                if(A[j]<A[i])dp[i]=max(dp[i],dp[j]+A[i]);
            }
            
        }
        sort(dp+1, dp+1+n);

        cout<<dp[n]<<endl;

    }
}
// 64 位输出请用 printf("%lld")

思路：动态规划

状态转移方程：

if(A[j]<A[i])dp[i]=max(dp[i],dp[j]+A[i]);