The longest ascending subsequence model acwing 1017. The glider wing of the strange thief Kidd

Longest ascending subsequence model AcWing 1017. Kidd's glider

Original link

AcWing 1017. Kidd's glider

Algorithm tags

DP linear DP Longest ascending subsequence

Ideas

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 = 105, INF = 0x3f3f3f3f;
int f[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 t=read();
	while(t--){
	    int n=read();
	    rep(i, 1, n+1){
	        a[i]=read();
	    }
	    int ans=0;
	    // a[i] End point   Pass from left to right a[j] The longest distance 
	    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);
	            }
	        }
	        ans=max(ans, f[i]);
	    }
	    // a[i] End point   Pass from right to left a[j] The longest distance 
	    Rep(i, n, 0){
	        f[i]=1;
	        Rep(j, n, i+1){
	            if(a[j]<a[i]){
	                f[i]=max(f[i], f[j]+1);
	            }
	        }
	        ans=max(ans, f[i]);
	    }
	    printf("%lld\n", ans);
	}
}

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