AcWing 1016. 最大上升子序列和
原题链接
简单
作者:
Chi
,
2022-07-05 11:26:48
,
所有人可见
,
阅读 195
王道机试指南 12.5 最大上升子序列和
代码
#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN = 1000;
int dp[MAXN];
int arr[MAXN];
int main(){
int n;
scanf("%d",&n);
for(int i = 0 ; i < n; i++){
scanf("%d",&arr[i]);
dp[i] = arr[i];//初始化为arr[i]
}
int answer = 0;
for(int i = 0;i < n;i++){
for(int j = 0 ; j < i ; j++){
if(arr[j]<arr[i]){
dp[i]=max(dp[i],dp[j]+arr[i]);//注意是dp[i],遍历j的时候dp[i]已发生了变化;
}
}
answer = max(answer,dp[i]);
}
cout<<answer;
}