两边算一下LIS就出来了，因为数据比较大，所以需要二分优化一下。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 7 const int maxn = 10000 + 10; 8 9 int n; 10 11 int a[maxn], l[maxn], r[maxn]; 12 int g[maxn]; 13 14 void LIS(int d[]) 15 { 16 memset(g, 0x3f, sizeof(g)); 17 for(int i = 0; i < n; i++) 18 { 19 int k = lower_bound(g+1, g+1+n, a[i]) - g; 20 d[i] = k; 21 g[k] = a[i]; 22 } 23 } 24 25 int main() 26 { 27 while(scanf("%d", &n) == 1) 28 { 29 for(int i = 0; i < n; i++) scanf("%d", a + i); 30 LIS(l); 31 reverse(a, a + n); 32 LIS(r); 33 34 int ans = 1; 35 for(int i = 0; i < n; i++) ans = max(ans, min(l[i], r[n-1-i])); 36 printf("%d ", ans * 2 - 1); 37 } 38 39 return 0; 40 }