C++ で最大部分配列とアルゴリズムを使用する方法

C での最大部分配列合計アルゴリズムの使用方法

最大部分配列合計問題は古典的なアルゴリズムの問​​題であり、指定された整数配列内で連続した部分配列を見つける必要があります。部分配列内のすべての要素の合計が最大になるようにします。この問題は動的計画法という考え方を使うことで解決できます。

シンプルですが非効率な解決策は、網羅的な方法ですべての可能な部分配列を見つけ、それらの合計を計算し、最大の合計を見つけることです。このメソッドの時間計算量は O(n^3) で、配列の長さが長い場合は非常に遅くなります。

より効率的なソリューションは、動的プログラミングの考え方に基づいています。補助配列 dp を定義することで、各要素で終わる部分配列の最大合計を記録できます。 dp[i] は、i 番目の要素で終わる最大の部分配列の合計を表します。 dp[i] については、2 つの状況があります。

1. dp[i-1] が 0 より大きい場合、dp[i] = dp[i-1] arr[i];
2. dp[i-1] が 0 以下の場合、dp[i] = arr[i]。

配列全体を走査することによって dp 配列の各要素を計算し、同時に最大の部分配列と max_sum、および対応する開始および終了添字 start および end を更新します。より大きな部分配列の合計が見つかった場合は、対応する値を更新します。最後に、サブ配列の最大合計は max_sum で、サブ配列の開始添字は start 、終了添字は end です。

以下は、C 言語で最大部分配列合計アルゴリズムを実装するコード例です:

#include <iostream>
#include <vector>

using namespace std;

vector<int> maxSubarraySum(vector<int>& arr) {
    int n = arr.size();
    int dp[n];
    dp[0] = arr[0];
    int max_sum = dp[0];
    int start = 0, end = 0;

    for(int i = 1; i < n; i++) {
        if(dp[i-1] > 0)
            dp[i] = dp[i-1] + arr[i];
        else {
            dp[i] = arr[i];
            start = i;
        }
        
        if(dp[i] > max_sum) {
            max_sum = dp[i];
            end = i;
        }
    }
    
    vector<int> result;
    result.push_back(max_sum);
    result.push_back(start);
    result.push_back(end);

    return result;
}

int main() {
    vector<int> arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    vector<int> result = maxSubarraySum(arr);
    
    cout << "最大子数组和：" << result[0] << endl;
    cout << "子数组的起始下标：" << result[1] << endl;
    cout << "子数组的终止下标：" << result[2] << endl;

    return 0;
}

上記のコードを実行すると、出力結果は次のようになります:

最大部分配列sum: 6
部分配列の開始添え字: 3
部分配列の終了添え字: 6

上記のコードは、動的計画法の考え方を通じて、O(n) の時間計算量で最大部分配列の合計を解きます。 。 質問。このアルゴリズムは、大規模な配列を扱う場合に非常に効率的です。

以上がC++ で最大部分配列とアルゴリズムを使用する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。