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

#include<iostream>
using namespace std;

const int maxn=1001;
int A[maxn];
int dp[maxn];

int main(){
	int n;
	while(cin>>n){
		for(int i=0;i<n;i++){
			cin>>A[i];
		}
		int maximum=0;
		for(int i=0;i<n;i++){
			dp[i]=A[i];		//初始化为A[i],以便后面直接用dp[i]进行比较
			for(int j=0;j<i;j++){
				if(A[j]<A[i]){
					dp[i]=max(dp[i],dp[j]+A[i]);
				}
			}
			maximum=max(maximum,dp[i]);
		}
		cout<<maximum<<endl;
	}
	return 0;
}