C++ で最長増加サブシーケンス アルゴリズムを使用する方法

C で最長増加部分列アルゴリズムを使用する方法には、特定のコード例が必要です。

最長増加部分列 (LIS) は古典的なアルゴリズムの問​​題であり、解決策のアイデアは次のとおりです。データ処理、グラフ理論などの多くの分野に応用されています。この記事では、C での最長増加部分列アルゴリズムの使用方法と具体的なコード例を紹介します。

まず、最長増加部分列の定義を理解しましょう。シーケンス a1、a2、…、an が与えられた場合、元のシーケンス内の b の要素の相対順序が増加している最長のサブシーケンス b1、b2、…、bm を見つける必要があります。つまり、任意の i ai が満たされる場合、b には bj > bi も存在します。最長の増加部分列の長さは m です。

次に、最長増加部分列を解くための 2 つの一般的なアルゴリズム、動的計画法アルゴリズムと貪欲アルゴリズムを紹介します。

1. 動的計画法アルゴリズム

動的計画法アルゴリズムは、最長増加部分列の解法プロセスを複数の段階に分割し、結果を 2 次元配列 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;
}

2. 貪欲アルゴリズム

貪欲アルゴリズムは、より効率的な方法です。最長の問題を解決する 後続問題を増やす方法。このアルゴリズムは、補助配列 d を使用して、現在の最長増加サブシーケンスの最後の要素を保存します。シーケンス全体をトラバースし、要素ごとに二分探索を使用して補助配列 d 内の位置を決定します。

具体的な解決プロセスは次のとおりです。

• 補助配列 d を空の配列として初期化します。
• シーケンス全体を左から右にたどって、要素 a ごとに、a が d の最後の要素より大きい場合は、d の最後に a を追加します。
• 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 中国語 Web サイトの他の関連記事を参照してください。