15-最长上升子序列（二分）

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int a[100005], c[100005];

int find(int low, int high, int x){
    while(low < high){
        int mid = (high + low) / 2;
        if(x < c[mid])
            high = mid;
        else
            low = mid + 1;
    }
    return low;
}

int main(){
    int n;
    while(~scanf("%d", &n)){
        memset(a, 0, sizeof(a));
        memset(c, 0, sizeof(c));
        for(int i = 0; i < n; i++)    
            scanf("%d", &a[i]);
        int len = 0;
        c[0] = a[0];
        for(int i = 1; i < n; i++){
            if(a[i] > c[len]){
                c[++len] = a[i];
            }
            else{
                int w = find(0, len, a[i]);
                c[w] = a[i];
            }
        }    
        printf("%d\n", len + 1);
    }
    return 0;
}

15-最长上升子序列（二分）

原文：http://www.cnblogs.com/zhumengdexiaobai/p/7429665.html