求两次最长上升/下降子序列即可。 由于数据范围是1e5，必须用nlogn的算法。 1.s[i]表示上升子序列长度为i的结尾最小的数。 2.s[i]单调上升 3.求<=a[i]的最大值的下标
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int N=1e5+10; int a[N]; int s[N];int n; bool judge() { int top=0; for(int i=1;i<=n;i++) { int pos=upper_bound(s+1,s+top+1,a[i])-s; s[pos]=a[i]; top=max(top,pos); } return top>=n-1; } int main() { int t; scanf("%d",&t); while(t--) { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); } bool flag=judge(); reverse(a+1,a+n+1); flag|=judge(); if(flag) printf("YES\n"); else printf("NO\n"); } }