目錄
一.最長遞增子序列問題I
二.最長遞增子序列問題II
三. 最長遞增子序列問題III
一.最長遞增子序列問題I
1.對(duì)應(yīng)牛客網(wǎng)鏈接
最長上升子序列(一)_?？皖}霸_?？途W(wǎng) (nowcoder.com)
2.題目描述：
?3.解題思路
1.首先我們分析題意：最長遞增子序列拆：要遞增的，還是序列，不一定連續(xù) ，要長度最長的。
2.子序列和子數(shù)組問題我們一般考慮必須以某個(gè)位置結(jié)尾如何如何，在本題中我們可以這樣考慮必須以i位置結(jié)尾的情況下最長遞增子序列的最大長度是多少我們每個(gè)位置都這么干那么答案一定就在其中
下面以[5,7,1,9,4,6,2,8,3]為例：
第一個(gè)元素 5： 遞增長度只能為1， 接下來第二個(gè)7，比5大，長度為2
?
第三個(gè)元素 1：前面沒有比它大的，只能為1 ， 第四個(gè)元素9，前面有5，7，故長度為3到這里你發(fā)現(xiàn)，9比7大，7往前構(gòu)成的長度是2，那9就可以接在7的后面，變成長度加一的新序列。
?我相信老鐵應(yīng)該懂了
4.對(duì)應(yīng)代碼：文章來源：http://www.zghlxwxcb.cn/news/detail-616478.html
class Solution { public: /** * 代碼中的類名、方法名、參數(shù)名已經(jīng)指定，請(qǐng)勿修改，直接返回方法規(guī)定的值即可 * * 給定數(shù)組的最長嚴(yán)格上升子序列的長度。 * @param arr int整型vector 給定的數(shù)組 * @return int整型 */ int LIS(vector<int>& arr) { if (arr.empty()) return 0; // write code here int N = arr.size(); vector<int>dp(N, 1);//每個(gè)位置最長遞增子序列的長度至少為1自己本身就是 //dp的含義是必須以i位置結(jié)尾的情況下最長遞增子序列的最大長度 int maxLen = 1; for (int i = 1; i < N; i++) { for (int j = 0; j < i; j++) { if (arr[i] > arr[j]) { dp[i] = max(dp[i], dp[j] + 1); //長度加1 } } maxLen = max(maxLen, dp[i]);//更新最大長度 } return maxLen; } };
二.最長遞增子序列問題II
1.對(duì)應(yīng)?？途W(wǎng)鏈接：
最長上升子序列(二)_?？皖}霸_牛客網(wǎng) (nowcoder.com)
2.題目描述：
?3.解題思路：
1.在這里我們引入end數(shù)組，end[i]的值為最目前為止長度為i+1的最小結(jié)尾
2.每次去end數(shù)組里面去找大于等于arr[i]最左的位置
?
我們看同樣是長度為2的子序列，[2,3]就比[2,5]好。因?yàn)閇2,3]后面如果有4的話，組成[2,3,4]長度就是3了，但是[2,5]因?yàn)椴粷M足條件，就沒法組隊(duì)了。
我們組成子序列的時(shí)候，不僅要讓這個(gè)序列盡可能的長，而且要讓子序列中的上升的時(shí)候盡可能的緩慢，[2,3]就比[2,5]上升的緩慢，這樣就有機(jī)會(huì)能拼接出更長的上升子序列。我們用一個(gè)數(shù)組來保存當(dāng)前的最長上升子序列，這個(gè)數(shù)組是嚴(yán)格遞增的。
因?yàn)槭菄?yán)格遞增的，數(shù)組中最后一個(gè)值nums[max]就是最大值，如果下次再碰到一個(gè)數(shù)字n，它比num[max]還要大，那么很明顯，這個(gè)子序列的長度就要+1，并且將數(shù)組n添加到數(shù)組的末尾。[2,3,7,8,11,13,18]是目前為止最長的上升子序列，之后如果又碰到了19，或者101，因?yàn)樗麄兌即笥跀?shù)組中的最大值18，所以直接將其添加到數(shù)組末尾就可以了，同時(shí)子序列的長度要+1。19和101的例子很好理解，但如果下次碰到的數(shù)字是6或者12呢？因?yàn)橐屪有蛄猩仙谋M可能緩慢，那么讓[2,5,7...]變成[2,5,6...]更合適，因?yàn)楹笳呱仙母徛Ｍ瑯?將[...8,11,13,18]變成[...8,11,12,18]也是上升的更緩慢一點(diǎn)。
也就是，已知上升子序列[i,i_1,i_2,....,i_n]，現(xiàn)在我們?cè)诶^續(xù)遍歷的過程中碰到了一個(gè)值i_k，這個(gè)值是小于i_n的，所以上升子序列的長度還是不變。但是我們需要找到一個(gè)位置，將i_k替換掉某個(gè)舊的值。對(duì)應(yīng)動(dòng)圖：
4.對(duì)應(yīng)代碼：
class Solution { public: /** * 代碼中的類名、方法名、參數(shù)名已經(jīng)指定，請(qǐng)勿修改，直接返回方法規(guī)定的值即可 * * 該數(shù)組最長嚴(yán)格上升子序列的長度 * @param a int整型vector 給定的數(shù)組 * @return int整型 */ int LIS(vector<int>& arr) { // write code here if (arr.empty()) { return 0; } int N = arr.size(); vector<int>end(N); //end[i]的含義是目前為止長度為i+1的最小結(jié)尾 end[0] = arr[0]; int L = 0; int maxLen = 1; int right = 0; //用于控制end數(shù)組的范圍 int R = right; for (int i = 1; i < N; i++) { L = 0; R = right; while (L <= R) {//用于查找大于等于arr[i]最左邊的位置 int mid = (L + R) >> 1; if (arr[i] > end[mid]) { L = mid + 1; } else { R = mid - 1; } } right = max(right, L); //更新右邊界 maxLen = max(maxLen, L + 1); end[L] = arr[i]; } return maxLen; } };
三. 最長遞增子序列問題III
1.對(duì)應(yīng)letecode鏈接：
最長上升子序列(三)_?？皖}霸_?？途W(wǎng) (nowcoder.com)
2.題目描述：
3.解題思路
1.本題只是上題的一個(gè)升級(jí)版我們只需要定義一個(gè)變量記錄?一下最長遞增子序列的結(jié)尾位置在哪里即可，然后再依次遍歷
4.對(duì)應(yīng)代碼：
class Solution { public: /** * retrun the longest increasing subsequence * @param arr int整型vector the array * @return int整型vector */ vector<int> LIS(vector<int>& arr) { // write code here if (arr.empty()) { return {}; } int N = arr.size(); vector<int>dp(N, 1); vector<int>end(N); int maxLen = 1; int maxIndex = 0; end[0] = arr[0]; int right = 0; int L = 0; int R = right; for (int i = 1; i < N; i++) { L = 0; R = right; while (L <= R) { int mid = (L + R) >> 1; if (arr[i] > end[mid]) { L = mid + 1; } else { R = mid - 1; } } right = max(right, L); maxLen = max(maxLen, L + 1); end[L] = arr[i]; dp[i] = L + 1; if (dp[i] >= maxLen) {//由于要求子典序最小 maxIndex = i; maxLen = dp[i]; } } vector<int>ans(maxLen);//獲取最長的遞增子序列 for (int i = maxIndex; i >= 0; i--) { if (dp[i] == maxLen) { ans[--maxLen] = arr[i]; } } return ans; } };
思考題：如果要獲取所有遞增子序列了？文章來源地址http://www.zghlxwxcb.cn/news/detail-616478.html
#include<iostream> #include<vector> using namespace std; vector<int> process(vector<int>& arr,vector<int>&dp ,int maxLen, int index) {//獲取所有最長遞增子序列 vector<int>ans(maxLen); for (int i = index; i >= 0; i--) { if (dp[i] == maxLen) { ans[--maxLen] = arr[i]; } } cout << "進(jìn)來" << endl; return ans; } int main() { int N; cin >> N; vector<int>arr(N); for (int i = 0; i < N; i++) { cin >> arr[i]; } vector<int>dp(N, 1); vector<int>end(N); int maxLen = 1; int maxIndex = 0; end[0] = arr[0]; int right = 0; int L = 0; int R = right; for (int i = 1; i < N; i++) { L = 0; R = right; while (L <= R) { int mid = (L + R) >> 1; if (arr[i] > end[mid]) { L = mid + 1; } else { R = mid - 1; } } right = max(right, L); maxLen = max(maxLen, L + 1); end[L] = arr[i]; dp[i] = L + 1; if (dp[i] >= maxLen) { maxIndex = i; maxLen = dp[i]; } } vector<vector<int>>ans; for (int i = 0; i < N; i++) { if (dp[i] == maxLen) { ans.push_back(process(arr, dp, maxLen, i)); } } for (int i = 0; i < ans.size(); i++) { for (int j = 0; j < ans[0].size(); j++) { cout << ans[i][j] << " "; } cout << endl; } return 0; }
到了這里，關(guān)于最長遞增子序列問題（你真的會(huì)了嗎）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
