题解 | #最大上升子序列和#
最大上升子序列和
http://www.nowcoder.com/practice/dcb97b18715141599b64dbdb8cdea3bd
【最长递增子序列】
dp[i]表示“以i结尾”(指必须取num[i])的最长递增子序列长度，因此结果可以累加到dp[n]，直接取dp[n]即可
【最大递增子序列和】
dp[i]表示“从0到i”(可以不取num[i])的最大递增子序列和，各自结果独立，因此需要求max
#include<iostream>
#include<math.h>
using namespace std;
int main(){
int n;
int num[1000];
int dp[1000];
while(cin>>n){
for(int i=0;i<n;i++){
cin>>num[i];
}
int maxSum = 0;
for(int i=0;i<n;i++){
dp[i] = num[i];
for(int j=0;j<i;j++){
if(num[i]>num[j]) dp[i] = max(dp[i],dp[j]+num[i]);
}
maxSum = max(maxSum,dp[i]);
}
cout<<maxSum<<endl;
}
return 0;
}
