最长单调递增子序列
问题描述
找出由n个数组成的序列的最长单调递增子序列。
示例输入
9
2 1 5 3 6 4 8 9 7
示例输出
5
示例输入
6
5 6 7 1 2 8
示例输出
4
c++代码(动态规划 O(n^2))
#include<bits/stdc++.h>using namespace std;int main() {int n, ans = 0;cin >> n;vector<int> arr(n), dp(n, 1);for (int i = 0; i < n; i++) cin >> arr[i];for (int i = 0; i < n; i++) {for (int j = i - 1; j >= 0; j--) {if (arr[i] > arr[j]) dp[i] = max(dp[i], dp[j] + 1);}}for (int i = 0; i < n; i++) ans = max(ans, dp[i]);cout << ans;return 0;
}
c++代码(贪心+二分 O(nlogn))
#include <bits/stdc++.h>using namespace std;int main() {int n;cin >> n;vector<int> arr(n);for (int i = 0; i < n; i++) cin >> arr[i];vector<int> ans;for (int i = 0; i < n; i++) {if (ans.size() == 0 || arr[i] > ans.back()) ans.push_back(arr[i]);else {auto k = lower_bound(ans.begin(), ans.end(), arr[i]);*k = arr[i];}}cout << ans.size();return 0;
}//by wqs
算法解析
动态规划法解析
dp[i]表示以i结尾的最长单调递增子序列的长度，则遍历i之前的dp[j]，如果arr[j] < arr[i]，说明arr[i]可以拼接在dp[j]的后面。
所以dp[i] = dp[j] + 1，考虑到有很多j，取最大值，dp[i] = max(dp[i], dp[j] + 1);
贪心+二分算法解析
考虑到最长单调子序列的单调递增，二分查询很快，所以有了这个算法。
我们尽量让序列越长越好，序列里面的数越小越好，为什么呢
例如
7 1 8 2 9 3 10 5
8 9 10不可以选5
而1 2 3可以选5
前面的数越小，后面的数加进来的概率越大
下面给出过程
7
1，由于7 > 1，不如替换为1，让后面的数容易加入序列
1 8
1 2，由于8 > 2不如替换为2，让后面的数容易加入序列
1 2 9
1 2 3，由于9 > 3，不如替换为3，让后面的数容易加入序列
1 2 3 10
1 2 3 5，由于10 > 5，不如替换为5，让后面的数容易加入序列
每次我们要加入一个数的时候
如果可以直接加入序列末尾，就加入序列末尾，
否则我们二分查找第一个大于或者等于它的位置，将那个位置换成它。
这样操作，后面的数中选率大
