f[i]表示的集合不变,与最长上升子序列相比最大上升子序列只不过是从求长度变为求数值
我们还是枚举上一个是哪个点,从那个点进行转移
原先的f[i] = 1,现在变为f[i] = a[i];(最少只选一个数)
f[i] = max(f[i],f[j] + 1) 变为 f[i] = max(f[i],f[j] + a[i])(加上当前权值)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1005;
int n;
int a[N],f[N];
int main(){
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> a[i];
for (int i = 1; i <= n; i ++ ){
f[i] = a[i];
for(int j=1;j<i;j++){
if(a[i] > a[j]){
f[i] = max(f[i],f[j] + a[i]);
}
}
}
int ans = 0;
for (int i = 1; i <= n; i ++ ) ans = max(ans,f[i]);
cout << ans;
return 0;
}