题目由leetcode1713延伸,求最长上升子序列,数据量较大时选中二分优化很快
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; #define inf 0x3f3f3f3f // int dp[200220], list[200220], a[200220]; // dp[i]保存lis为i时最小的元素,list保存每个元素的lis; int dp[10], list[10], a[10]; // dp[i]保存lis为i时最小的元素,list[i]:保存以a[i]元素结尾的lis长度; int main() { int n, i, j, k, p; while (cin >> n) { int p = 0; memset(dp, inf, sizeof(dp)); for (i = 0; i < n; i++) { scanf("%d", &a[i]); *lower_bound(dp, dp + n, a[i]) = a[i]; // 记录更新长度对应的最大潜力元素时,顺便记录下该元素对应的LIS长度 list[p++] = lower_bound(dp, dp + n, a[i]) - dp + 1; } k = lower_bound(dp, dp + n, inf) - dp; // k:总的LIS长度 cout << k << endl; int m = k; for (i = n - 1; i >= 0; i--) { // 从右至左扫描一遍直至找全LIS长度 if (k == list[i]) dp[k--] = a[i]; if (!k) break; } for (i = 1; i <= m; i++) printf("%d\n", dp[i]); } return 0; }