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

最大上升子序列和（不一定连续）

思路：统计以s[i]结尾的上升子序列的和sum[i]

分为2类：是否比前面所有元素都小

• ①是 前面序列对其没有贡献:sum[i]=s[i]
• ②否 前面序列对其有贡献:sum[i]=max(sum[j]+s[i])（需遍历s[i]前面所有元素，保留最大值）

#include<iostream>
using namespace std;

const int maxn=1001;

int s[maxn];
int sum[maxn];//上升子序列的和

int longest(int n){
  int ans=0;//最大上升子序列和
  for(int i=0;i<n;i++){
    sum[i]=s[i];
    for(int j=0;j<i;j++){
      if(s[i]>s[j])sum[i]=max(sum[i],sum[j]+s[i]);
    }
    
    ans=max(ans,sum[i]);
  }
  return ans;
}


int main(){
  int n;
  while(scanf("%d",&n)!=EOF){
    for(int i=0;i<n;i++){
      scanf("%d",&s[i]);
    }
    printf("%d\n",longest(n));
  }
  
  return 0;
}