如何使用C 中的最長遞增子序列演算法,需要具體程式碼範例
最長遞增子序列(Longest Increasing Subsequence,簡稱LIS)是一個經典的演算法問題,其解決思路可應用於多個領域,如資料處理、圖論等。在本文中,我將為大家介紹如何使用C 中最長的遞增子序列演算法,並提供具體的程式碼範例。
首先,我們來了解最長遞增子序列的定義。給定一個序列a1, a2, …, an,我們需要找到一個最長的子序列b1, b2, …, bm,其中b的元素在原序列中的相對順序是遞增的。也就是說,對於任意的i ai,那麼在b中也有bj > bi。最長遞增子序列的長度即為m。
接下來,我們將介紹兩種常見的求解最長遞增子序列的演算法:動態規劃演算法和貪心演算法。
動態規劃演算法將最長遞增子序列的求解過程分成多個階段,並將結果儲存在一個二維數組dp中。 dp[i]表示以序列中第i個元素結尾的最長遞增子序列的長度。
具體求解過程如下:
最終的結果為dp陣列中的最大值。
以下是用C 實作動態規劃演算法的程式碼範例:
#include<iostream> #include<vector> using namespace std; int longestIncreasingSubsequence(vector<int>& nums) { int n = nums.size(); vector<int> dp(n, 1); for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++) { if (nums[j] < nums[i]) { dp[i] = max(dp[i], dp[j]+1); } } } int res = 0; for (int i = 0; i < n; i++) { res = max(res, dp[i]); } return res; } int main() { vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18}; int res = longestIncreasingSubsequence(nums); cout << "最长递增子序列的长度为:" << res << endl; return 0; }
貪心演算法是一種更有效率的解決最長遞增子序列問題的方法。此演算法利用一個輔助數組d來保存目前最長遞增子序列的末尾元素。遍歷整個序列,對於每個元素,使用二分查找的方式確定其在輔助數組d中的位置。
具體求解過程如下:
最終的結果為輔助數組d的長度。
下面是用C 實作貪心演算法的程式碼範例:
#include<iostream> #include<vector> using namespace std; int longestIncreasingSubsequence(vector<int>& nums) { vector<int> d; for (auto num : nums) { int left = 0, right = d.size() - 1; while (left <= right) { int mid = left + (right - left) / 2; if (d[mid] < num) { left = mid + 1; } else { right = mid - 1; } } if (left >= d.size()) { d.push_back(num); } else { d[left] = num; } } return d.size(); } int main() { vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18}; int res = longestIncreasingSubsequence(nums); cout << "最长递增子序列的长度为:" << res << endl; return 0; }
以上就是如何使用C 中的最長遞增子序列演算法的介紹和程式碼範例。無論是動態規劃演算法或貪心演算法,都可以在時間複雜度為O(n^2)或O(nlogn)的情況下解決最長遞增子序列問題。讀者可以根據具體的應用場景選擇合適的演算法來使用。希望本文能對大家了解最長遞增子序列演算法提供協助。
以上是如何使用C++中最長的遞增子序列演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章!