The longest ascending subsequence model acwing 1014 Mountaineering

Longest ascending subsequence model AcWing 1014. Mountaineering

Original link

AcWing 1014. Mountaineering

Algorithm tags

DP linear DP Longest ascending subsequence

Ideas

Ask for i Ending ascending sequence , With i The reverse rising at the end is the descending sequence , With i It is a sequence in which the dividing point rises first and then falls , Find the maximum .

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, 1, n+1){
	    a[i]=read();
	}
	int ans=0, ans1=0, ans2=0;
	//  With i Ending ascending sequence 
	rep(i, 1, n+1){
	    f[i]=1;
	    rep(j, 1, i){
	        if(a[j]<a[i]){
	            f[i]=max(f[i], f[j]+1);
	        }
	    }
	    ans1=max(ans1, f[i]);
	}
	//  With i The reverse rising at the end is the descending sequence 
	Rep(i, n, 0){
	    f1[i]=1;
	    Rep(j, n, i+1){
	        if(a[j]<a[i]){
	            f1[i]=max(f1[i], f1[j]+1);
	        }
	    }
	    ans2=max(ans2, f1[i]);
	}
	//  Go up first   Post descent sequence 
	rep(i, 1, n+1){
	    ans=max(ans, f[i]+f1[i]-1);
	}
	printf("%lld\n", max({ans, ans1, ans2}));
}

And y The general code is consistent

y Master code

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n;
int h[N];
int f[N], g[N];

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

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

    for (int i = n - 1; i >= 0; i -- )
    {
        g[i] = 1;
        for (int j = n - 1; j > i; j -- )
            if (h[i] > h[j])
                g[i] = max(g[i], g[j] + 1);
    }

    int res = 0;
    for (int i = 0; i < n; i ++ ) res = max(res, f[i] + g[i] - 1);

    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