題意：

找一個最長（假設長度為2N-1）的子序列，使得前N個元素遞增，后N個元素遞減。

思路：

用nlogn的方法首尾各求一遍LIS,然后枚舉中點就可以了。

注意要求中點兩邊一樣長。

代碼：

#include<iostream>#include<cstdio>#include<cstring>using namespace std;const int maxn = 1e5+5;int n, a[maxn], b[maxn], dp1[maxn], dp2[maxn];int main(void){    while(cin >> n)    {        for(int i = 1; i <= n; i++)            scanf("%d", &a[i]);        int len = 1, l, r;        b[1] = a[1];        for(int i = 1; i <= n; i++)        {            l = 1, r = len;            while(l <= r)            {                int mid = (l+r)/2;                if(b[mid] < a[i]) l = mid+1;                else r = mid-1;            }            b[l] = a[i];            dp1[i] = l;            if(l > len) len++;        }        b[1] = a[n];        len = 1;        for(int i = n; i >= 1; i--)        {            l = 1, r = len;            while(l <= r)            {                int mid = (l+r)/2;                if(b[mid] < a[i]) l = mid+1;                else r = mid-1;            }            b[l] = a[i];            dp2[i] = l;            if(l > len) len++;        }        int ans = 0;        for(int i = 1; i <= n; i++)            if(min(dp1[i], dp2[i])*2-1 > ans)                ans = min(dp1[i], dp2[i])*2-1;        PRintf("%d/n", ans);    }    return 0;}