POJ.2533 Longest Ordered Subsequence

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

2.Idea
dp[k]: the length of longest sub ordered sequence that ends at s[i].
dp[i] = max{dp[j] + 1 | j=0..i-1}

3.Source

 
 int dp[1003];  
 int a[1003];  
 int n;  
 int main()  
 {  
      cin >> n;  
      for (int i = 0; i < n; i++) {  
           cin >> a[i];  
      }  
      dp[0] = 1;  
      int ans = 1;  
      for (int i = 1; i < n; i++) {  
           dp[i] = 1;  
           for (int j = 0; j < i; j++) {  
                if (a[j] < a[i]) dp[i] = max(dp[i], dp[j] + 1);  
           }  
           ans = max(ans, dp[i]);  
      }  
      cout << ans << endl;  
      return 0;  
 }