最长上升子序列(LIS)

 1 int dp[MAX_N], a[MAX_N], n;
 2 int ans = 0;  // 保存最大值
 3 
 4 for (int i = 1; i <= n; ++i) {
 5     dp[i] = 1;
 6     for (int j = 1; j < i; ++j) {
 7         if (a[j] < a[i]) {
 8             dp[i] = max(dp[i], dp[j] + 1);
 9         }
10     }
11     ans = max(ans, dp[i]);
12 }
13 
14 cout << ans << endl;  // ans 就是最终结果

O(n^2)

 1 int ans[MAX_N], a[MAX_N], dp[MAX_N], n;  // ans 用来保存每个 dp 值对应的最小值，a 是原数组
 2 int len; // LIS 最大值
 3 
 4 ans[1] = a[1];
 5 len = 1;
 6 
 7 for(int i = 1;i <= n; i++) ans[i] = INF;
 8 
 9 for (int i = 1; i <= n; ++i) {
10     if (a[i] < ans[len]) {
11         ans[++len] = a[i];
12     } else {
13         int pos = lower_bound(ans + 1, ans + len + 1, a[i]) - ans;
14         ans[pos] = a[i];
15     }
16 }
17 
18 cout << len << endl;  // len 就是最终结果

O(nlogn)