描写叙述

给定一整型数列{a₁,a₂...,a_n}（0<n<=100000），找出单调递增最长子序列。并求出其长度。

如：1 9 10 5 11 2 13的最长单调递增子序列是1 9 10 11 13，长度为5。

输入

有多组測试数据（<=7）

每组測试数据的第一行是一个整数n表示序列中共同拥有n个整数。随后的下一行里有n个整数，表示数列中的全部元素.每一个整形数中间用空格间隔开（0<n<=100000）。

数据以EOF结束 。

输入数据保证合法（全为int型整数）。

输出

对于每组測试数据输出整形数列的最长递增子序列的长度，每一个输出占一行。

例子输入

7

1 9 10 5 11 2 13

2

2 -1

例子输出

5

1

分析：跟hdoj1025原理http://blog.csdn.net/shengweisong/article/details/40347947一样

代码：

#include <stdio.h>

#include <string.h>

#include <algorithm>

#define M 100005

using namespace std;

int a[M], d[M];

int bis(int m, int len){

    int left = 1, right = len, mid;

    while(left <= right){

        mid = (right+left)>>1;

        if(d[mid] > m) right = mid-1;

        else if(d[mid]< m) left = mid+1;

        else return mid;

    }

    return left;

}

int main(){

    int n;

    while(~scanf("%d", &n) ){

        memset(d, 0, sizeof(d));

        int i, len;

        for(i = 0; i < n; i ++){

            scanf("%d", &a[i]);

        }

        //sort(a, a+n);

        len = 1;

        d[len] = a[i];

        for(i = 1; i < n; i ++){

            int t = bis(a[i], len);

            d[t] = a[i];

            if(t>len) len++;

        }

        printf("%d\n", len);

    }

    return 0;

}