最長單調遞增子序列
問題描述
找出由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，讓后面的數容易加入序列
每次我們要加入一個數的時候
如果可以直接加入序列末尾，就加入序列末尾，
否則我們二分查找第一個大于或者等于它的位置，將那個位置換成它。
這樣操作，后面的數中選率大
