NYOJ 214 單調遞增子序列

描述
給定一整型數列{a1,a2...,an}（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開始的時候以為和“單調遞增子序列一”http://blog.csdn.net/xiangguangde/article/details/8824114
差不多，只是數據大了，感覺會如果再用那個方法會超時，但是還是心存僥幸，試試吧，結果果斷TLE了；
後來經過隊友的指點，用有序數組存儲序列，二分查找終於AC了，期間還出了點小差錯RE了一次，因為
沒有注意到題中還會有負數，f數組初始化為0是不夠的
[cpp]
#include <algorithm>  
#include <iostream>  
#include <cstring>  
#include <cstdlib>  
#include <string>  
#include <vector>  
#include <cstdio>  
#include <cmath>  
#include <map>  
#define FLAG 0  
#define M 100000+10  
using namespace std; 
int a[M]; 
int f[M]; 
 
void midfs(int beg, int end,int n) 
{ 
    int mid=(beg+end)/2; 
    if(f[mid]==n)return ; 
    if(beg==end){f[end]=n;return ;} 
    if(n>f[mid]) 
    { 
        midfs(mid+1,end,n); 
    } 
    else midfs(beg,mid,n); 
} 
 
int main() 
{ 
    #if(FLAG)  
        freopen("in.txt", "r", stdin); 
        //freopen("out.txt", "w", stdout);  
    #endif  
    int n,i,j,flag; 
    while(cin>>n) 
    { 
        flag=1; 
        memset(f,0,sizeof(f)); 
        f[0]=1<<31;           //是最小的負數,最開始因為沒有初始化f[0]為最小，RE了  
        for(i=1;i<=n;i++) 
        { 
            scanf("%d",&a[i]);//因為題中有負數，初始化f為0後如果輸入的第一個數是負數  
            if(a[i]>f[flag-1])f[flag++]=a[i];//將不執行這一句，進入二分，然後死循環！  
            else 
            { 
                midfs(1,flag-1,a[i]); 
            } 
        } 
        printf("%d\n",flag-1); 
    } 
 
    return 0; 
}