The longest ascending subsequence model acwing 1016. The sum of the largest ascending subsequence

Longest ascending subsequence model AcWing 1016. The maximal ascending subsequence and

Original link

AcWing 1016. The maximal ascending subsequence and

Algorithm tags

DP linear DP Longest ascending subsequence

Ideas

Analog maximum ascending subsequence length , take f[i] Initialize to a[i]; f[i] Updated to f[i] And f[j]+a[i] The maximum value in .

Code

#include<bits/stdc++.h>
#define int long long
#define rep(i, a, b) for(int i=a;i<b;++i)
#define Rep(i, a, b) for(int i=a;i>=b;--i)
using namespace std;
const int N = 1005, INF = 0x3f3f3f3f;
int f[N], f1[N], a[N];
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
void put(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>=10) put(x/10);
    putchar(x%10^48);
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n=read();
	rep(i, 0, n){
	    a[i]=read();
	}
	int ans=0;
	//  With i Ending ascending sequence 
	rep(i, 0, n){
	    f[i]=a[i];
	    rep(j, 0, i){
	        if(a[j]<a[i]){
	            f[i]=max(f[i], f[j]+a[i]);
	        }
	    }
	    ans=max(ans, f[i]);
	}
	printf("%lld\n", ans);
}

And y The general idea is the same

y Master code

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n;
int w[N];
int f[N];

int main()
{
    scanf("%d", &n);

    for (int i = 0; i < n; i ++ ) scanf("%d", &w[i]);

    int res = 0;
    for (int i = 0; i < n; i ++ )
    {
        f[i] = w[i];
        for (int j = 0; j < i; j ++ )
            if (w[i] > w[j])
                f[i] = max(f[i], f[j] + w[i]);
        res = max(res, f[i]);
    }

    printf("%d\n", res);

    return 0;
}

Originality is not easy.
Reprint please indicate the source
If it helps you Don't forget to praise and support