【题意】给定N≤105的一个序列,现在有一个deque唯一的要求是deque里的数必须是不降的,求deque里的最多元素个数是多少

【解题方法】


【AC 代码】

#include <bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=100010;
int n,a[maxn];
int f[2][maxn],dp[maxn]; //start from i, 0 for longest non-increasing, 1 for longest non-decreasing
int same[2][maxn]; //start from i, in LIS sequence, same as a[i]
void solve(int *f,int *same)
{
    memset(dp,inf,sizeof(dp));
    for(int i=n; i>=1; i--){
        f[i]=upper_bound(dp+1,dp+n+1,a[i])-dp;
        dp[f[i]]=a[i];
        auto range=equal_range(dp+1,dp+n+1,a[i]);
        same[i]=range.second-range.first;
    }
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i=1; i<=n; i++) scanf("%d",&a[i]);
        solve(f[0],same[0]);
        for(int i=1; i<=n; i++) a[i]=-a[i];
        solve(f[1],same[1]);
        int ans=0;
        for(int i=1; i<=n; i++){
            ans=max(ans,f[0][i]+f[1][i]-min(same[0][i],same[1][i]));
        }
        printf("%d\n",ans);
    }
}