POJ-2533.Longest Ordered Subsequence (LIS模版题)

 1 #include <iostream>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 const int maxn = 1e3 + 5;
 7 int a[maxn], dp[maxn];
 8 
 9 int main () {
10     int n, ans = 0;
11     cin >> n;
12     for(int i = 1; i <= n; i ++)
13         cin >> a[i];
14     for(int i = 1; i <= n; i ++) {
15         dp[i] = 1;
16         for(int j = 1; j < i; j ++) {
17             if(a[i] > a[j]) dp[i] = max(dp[i], dp[j] + 1);
18         }
19         ans = dp[i] > ans ? dp[i] : ans;
20     }
21     cout << ans << endl;
22     return 0;
23 }