目錄
一.最長遞增子序列問題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)楹笳呱仙母徛M瑯?將[...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)!