1 #include<stdio.h> 2 int a[1000] , temp[1000] ; 3 int n , top ; 4  5 int binary_search (int x) { 6     int fir = 0 ; 7     int last = top ; 8     int mid ; 9     while (fir <= last ) {10         mid = (fir + last) / 2 ;11         if ( x <= temp[mid] ) {12             last = mid - 1;13         }14         else {15             if (x <= temp[mid + 1] )16                 return mid + 1 ;17             else18                 fir = mid + 1 ;19         }20     }21 }22 23 int main () {24   //  freopen ("a.txt" ,"r" , stdin) ;25     while ( scanf ("%d" , &n ) != EOF ) {26         for (int i = 0 ; i < n ; i++ ) {27             scanf ("%d" , &a[i]) ;28         }29 30         top = 0 ;//目前最长不下降子序列的长度31         temp[top] = a[0] ;////temp[i]为长度为i的上升子序列末尾元素的最小值32         for (int i = 1 ; i < n ; i++ ) {33             if ( a[i] >= temp[top] ) {34                 temp[++top] = a[i] ;35             }36             else {37                 if ( a[i] < temp[0] ) {38                     temp[0] = a[i] ;39                 }40                 else {41                     temp[binary_search(a[i])] = a[i] ;42                 }43             }44         }45         printf ("%d\n" , top + 1) ;46     }47     return 0 ;48 }