POJ. 1631 Bridging signals

1.Problem
http://poj.org/problem?id=1631

2.Idea
We can solve this problem with LIS(Longest Increasing Subsequence).

3.Source

 int t, n;  
 int p[40004];  
 int dp[40004];  
 int lis(int *p, int n) //longest increasing subsequence  
 {  
      for (int i = 0; i < n; i++) dp[i] = INF;  
      for (int i = 0; i < n; i++) {  
           *lower_bound(dp, dp + n, p[i]) = p[i];  
      }  
      return lower_bound(dp, dp + n, INF) - dp;  
 }  
 int main()  
 {  
      cin >> t;  
      while (t) {  
           cin >> n;  
           for (int i = 0; i < n; i++) scanf("%d", &p[i]);  
           printf("%d\n", lis(p, n));  
           t--;  
      }  
      return 0;  
 }