学步园

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
typedef long long   LL;
#define INF 1200000000
const int maxn  = 1100;
int S[maxn],g[maxn],n,d[maxn],fff;
void print_ans(int i){
if(fff) return ;
int res=0;
for(int j=0;j<i;j++) if(d[j]+1==d[i] && S[j]<S[i]) res++;
if(res>=2) {
    fff=1; return;
}
for(int j=0;j<i;j++) if(d[j]+1==d[i] && S[j]<S[i]){
    print_ans(j);  break;
}
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i=0;i<n;i++) scanf("%d",&S[i]);
        for(int i=1;i<=n;i++) g[i]=INF;
        int flag=0,ans=0;
        for(int i=0;i<n;i++){
            int k=lower_bound(g+1,g+n+1,S[i]) - g;
            d[i] = k;
            g[k] = S[i];
            ans  = max(ans,d[i]);
        }
        int num = ans;
        int posi=1;
        for(int i=0;i<n;i++) if(d[i]==ans) {flag++; posi=i;}
        if(flag>1){
                printf("%d\n",ans);
        }
        else {
               fff=0;
               print_ans(posi);
               if(fff) printf("%d\n",ans);
               else
               printf("%d\n",ans-1);
        }
    }
    return 0;
}

LIC 求second longest 路径 神坑 数据

3

1 1 2

3

3 1 2