首頁 > 後端開發 > C++ > 主體

如何使用C++中最長的遞增子序列演算法

王林
發布: 2023-09-19 17:21:34
原創
1690 人瀏覽過

如何使用C++中最長的遞增子序列演算法

如何使用C 中的最長遞增子序列演算法,需要具體程式碼範例

最長遞增子序列(Longest Increasing Subsequence,簡稱LIS)是一個經典的演算法問題,其解決思路可應用於多個領域,如資料處理、圖論等。在本文中,我將為大家介紹如何使用C 中最長的遞增子序列演算法,並提供具體的程式碼範例。

首先,我們來了解最長遞增子序列的定義。給定一個序列a1, a2, …, an,我們需要找到一個最長的子序列b1, b2, …, bm,其中b的元素在原序列中的相對順序是遞增的。也就是說,對於任意的i ai,那麼在b中也有bj > bi。最長遞增子序列的長度即為m。

接下來,我們將介紹兩種常見的求解最長遞增子序列的演算法:動態規劃演算法和貪心演算法。

  1. 動態規劃演算法

動態規劃演算法將最長遞增子序列的求解過程分成多個階段,並將結果儲存在一個二維數組dp中。 dp[i]表示以序列中第i個元素結尾的最長遞增子序列的長度。

具體求解過程如下:

  • 初始化dp陣列的所有元素為1,表示以每個元素結尾的子序列長度至少為1。
  • 從左到右遍歷整個序列,對於每個位置i,計算dp[i]的值。
  • 對於每個位置i,遍歷其前面位置j,如果aj

最終的結果為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;
}
登入後複製
  1. 貪心演算法

貪心演算法是一種更有效率的解決最長遞增子序列問題的方法。此演算法利用一個輔助數組d來保存目前最長遞增子序列的末尾元素。遍歷整個序列,對於每個元素,使用二分查找的方式確定其在輔助數組d中的位置。

具體求解過程如下:

  • 初始化輔助數組d為空數組。
  • 從左到右遍歷整個序列,對於每個元素a,如果a大於d的末尾元素,則將a添加到d的末尾。
  • 如果a小於等於d的末尾元素,則使用二分查找的方式找到d中大於等於a的第一個元素,並將其替換為a。

最終的結果為輔助數組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中文網其他相關文章!

來源:php.cn
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板