该题是最裸的LIS题，这里有两种方法。

代码如下：

#include 
     
       #include 
      
        #include 
       
         using namespace std; int a[10000], dp[10004]; int main() {
   int N; while (scanf("%d", &N) == 1)     {
   int ans = 1, m; for (int i = 0; i < N; ++i)         {
               scanf("%d", a+i);         }         dp[0] = 1; for (int i = 1; i < N; ++i)         {
               m = 0; for (int j = 0; j < i; ++j)             {
   if (a[i] > a[j] && dp[j] > m)                 {
                       m = dp[j];                 }             }             dp[i] = m+1;             ans = max(ans, dp[i]);         }         printf("%d\n", ans);     } }
       
      
     

二分优化后的写法，数组c[i]保留长度为i的上升串的末尾最小元素。

代码如下：

#include 
     
       #include 
      
        #include 
       
         #define MAXN 10000 using namespace std; int a[MAXN+5]; int bsearch(int *c, int l, int r, int val) {
   int mid; while (l <= r)     {
           mid = (l+r)>>1; if (val > c[mid])             l = mid + 1; else if (val < c[mid])             r = mid - 1; else  // 如果不是严格的递增序列的话，二分查找时，相等视为后者比其大             return mid;     } return l; } int LIS(int *a, int N) {
   int c[MAXN], size = 1, pos;     c[1] = a[0]; for (int i = 1; i < N; ++i)     {
   if (a[i]>c[size])             pos = ++size; else             pos = bsearch(c, 1, size, a[i]); // 返回比该值稍微大的点         c[pos] = a[i];     } return size; } int main() {
   int N; while (scanf("%d", &N) == 1)     {
   for (int i = 0; i < N; ++i)         {
               scanf("%d", &a[i]);         }         printf("%d\n", LIS(a, N));     } }