UVA 10534 Wavio Sequence LIS(nlogn实现) - c++编程基础

题意：求一个序列，找出先递增n个后递减n个的最长序列。

其实就是LIS的变形，跟以前的一题打导弹的题目差不多，不过这次的范围是10000，如果用以前那种朴素的DP算法，复杂度是O(n*n)果断会超时。。。

于是去学了nlogn的求LIS算法，其实就是维护一个递增序列，每次与序列最后面数字比较，如果能放后面就放后面，不能的话在前面二分找到适合的差不多的数字给换掉。

代码：

#include   
#include   
  
#define min(a, b) ((a) < (b)   (a) : (b))  
  
const int MAXN = 10010;  
  
int n, t, top;  
int nu[MAXN];  
int stk[MAXN];  
int a1[MAXN], a2[MAXN];  
  
int main() {  
    while (scanf("%d", &n) != EOF) {  
        for (int i = 0; i < n; i++)  
            scanf("%d", &nu[i]);  
        stk[0] = nu[0];  
        a1[0] = a2[0] = 1;  
  
        top = 1;  
        for (int i = 1; i < n; i++) {  
            if (nu[i] > stk[top - 1])  
                stk[top++] = nu[i];  
            else {  
                int low = 0, high = top - 1, mid;  
                while (low <= high) {  
                    mid = low + ((high - low) >> 1);  
                    if (nu[i] >




 stk[mid])  
                        low = mid + 1;  
                    else  
                        high = mid - 1;  
                }  
                stk[low] = nu[i];  
            }  
            a1[i] = top;  
        }  
  
        stk[0] = nu[n - 1];  
        top = 1;  
        for (int i = n - 1; i >= 1; i--) {  
            if (nu[i] > stk[top - 1])  
                stk[top++] = nu[i];  
            else {  
                int low = 0, high = top - 1, mid;  
                while (low <= high) {  
                    mid = low + ((high - low) >> 1);  
                    if (nu[i] > stk[mid])  
                        low = mid + 1;  
                    else  
                        high = mid - 1;  
                }  
                stk[low] = nu[i];  
            }  
            a2[i] = top;  
        }  
        int ans = 0;  
        for (int i = 0; i < n; i++) {  
            if (ans < min(a1[i], a2[i]))  
                ans = min(a1[i], a2[i]);  
        }  
        printf("%d\n", ans * 2 - 1);  
    }  
    return 0;  
}