题目链接：

题意：

求一个奇数长的子序列，前一半严格递增，后一半严格递减；O(nlogn)

 

分析：

再次复习一下LIS算法；

严格递增：

g[k] ： d[]值为 k　的最小元素，由于是严格递增，也就是说二分下界low_bound；

最长不下降：

也就是说upper_bound；

解析：二分函数，返回值是[L,R)，也就是说不下降的时候，就是在后面插入一个；

1 #include 
      
        2  3 using namespace std; 4  5 const int inf = 0x3f3f3f3f; 6 const int maxn = 10000 + 5; 7 int a[maxn]; 8 int b[maxn]; 9 int d[maxn];10 int p[maxn];11 12 int g[maxn];13 14 int main()15 {16     int n;17     while(scanf("%d",&n)!=EOF) {18         for(int i=0;i
       
        a[j])29         //            d[i] = max(d[i],d[j]+1);30         //}31 32         memset(g,inf,sizeof(g));33         for(int i=0;i
        
         =0;i--) {40         //    for(int j=n-1;j>i;j--) {41         //        if(a[i]>a[j])42         //            p[i] = max(p[i],p[j]+1);43         //    }44         //}45         memset(g,inf,sizeof(g));46         for(int i=n-1;i>=0;i--) {47             int k = lower_bound(g+1,g+n+1,a[i])-g;48             p[i] = k;49             g[k] = a[i];50         }51 52         int ans = 1;53         for(int i=0;i