题目描述
数据范围
1≤N≤1000
输入样例:
7
1 7 3 5 9 4 8
输出样例:
18
DP
(最长上升子序列模型) $O(n^2)$
就是最长的集合(f[N])初始化为1(f[i]=1),最大的集合(f[N])初始化为f[i]=w[i]
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N=1010;
int f[N],w[N];
int n;
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d",&w[i]);
for(int i=0;i<n;i++){
f[i]=w[i]; //跟最长子序列不一样的就是将集合f[N]初始化为当前位置的权重
for(int j=0;j<i;j++)
if(w[i]>w[j])
f[i]=max(f[i],f[j]+w[i]);
}
int res=0;
for(int i=0;i<n;i++)
res=max(res,f[i]);
printf("%d",res);
return 0;
}