DP经典之 CODE[VS] 1576 最长严格上升子序列（O(n^2) 和 O(nlogn)）

O(n^2):

 1 /*
 2 
 3 最长严格上升子序列
 4 dp[i] : 以第i个整数结尾的最长严格上升子序列长度
 5 dp[i] = max(dp[x]) + 1
 6 注： x < i && arr[x] < arr[i]
 7 
 8 */
 9 
10 #define _CRT_SECURE_NO_WARNINGS
11 #include <iostream>
12 #include <cstdio>
13 #include <cstdlib>
14 #include <cmath>
15 #include <string>
16 #include <algorithm>
17 #include <cstring>
18 #include <set>
19 #include <utility>
20 #include <locale>
21 #include <ctime>
22 using namespace std;
23 //using int64 = long long;
24 const int INF = 0x3f3f3f3f;
25 const int MaxN = 5010;
26 
27 int arr[MaxN];
28 int dp[MaxN];
29 
30 void Solve()
31 {
32 }
33 
34 int main()
35 {
36 
37     int len = 0;
38     cin >> len;
39     for (int i = 0; i < len; ++i) cin >> arr[i];
40     fill(dp, dp + len, 1);
41     for (int i = 0; i < len; ++i)
42     {
43         for (int j = 0; j < i; ++j)
44         {
45             if (arr[j] < arr[i]) dp[i] = max(dp[i], dp[j] + 1);
46         }
47     }
48     cout << *max_element(dp, dp + len) << endl;
49 
50 
51 #ifdef HOME
52     cerr << "Time elapsed: " << clock() / CLOCKS_PER_SEC << " ms" << endl;
53 #endif
54     return 0;
55 }

O(nlogn):

 1 /*
 2 最长严格上升子序列 O(nlogn)
 3 dp[i] : 长度为i+1的上升子序列中末尾元素的最小值（不存在的话，就是INF）
 4 */
 5 
 6 #include <iostream>
 7 #include <cstdio>
 8 #include <cstdlib>
 9 #include <cmath>
10 #include <string>
11 #include <algorithm>
12 #include <cstring>
13 #include <set>
14 #include <utility>
15 #include <locale>
16 #include <limits>
17 #include <ctime>
18 using namespace std;
19 //using int64 = long long;
20 const int INF = numeric_limits<int>::max();
21 const int MaxN = 5010;
22 
23 int N, arr[MaxN];
24 int dp[MaxN];
25 
26 void Solve()
27 {
28     fill(dp, dp + N, INF);
29     for (int i = 0; i < N; ++i)
30     {
31         *lower_bound(dp, dp + N, arr[i]) = arr[i];
32     }
33     cout << lower_bound(dp, dp + N, INF) - dp << endl;
34 }
35 
36 int main()
37 {
38     
39     cin >> N;
40     for (int i = 0; i < N; ++i) cin >> arr[i];
41     Solve();
42 
43 #ifdef HOME
44     cerr << "Time elapsed: " << clock() / CLOCKS_PER_SEC << " ms" << endl;
45 #endif
46     return 0;
47 }

注：

（1）lower_bound(arr, arr + len, k)：二分搜索，返回指向满足arr[i]>=k的最小指针。

详细参考这里：点击

实例参考这里：点击

（2）求int类型最大值：const int INF = numeric_limits<int>::max()。详细参考这里：点击

不可以设为0x3f3f3f3f，因为测试数据整数值已经超过ox3f3f3f3f:

0x3f3f3f3f化为10进制：1061109567

测试数据：

DP经典 之 CODE[VS] 1576 最长严格上升子序列 （O(n^2) 和 O(nlogn)）

DP经典之 CODE[VS] 1576 最长严格上升子序列（O(n^2) 和 O(nlogn)）