0

最大サブアレイ問題を研究しています。核となる考えを理解していないようです。次の配列があるとしましょう:int arr[] ={10, 4, 2, 12, 16, 1}サブ配列の最大値と最大値は 2 (3 番目の要素) と 16 (5 番目の要素) であるため、最大のサブ配列は 14 に等しくなければならないことがわかりました。まあ、どうやらそうではありません。ここで見つけた線形時間アルゴリズムを実装しました: http://heliang.me/wiki/index.php?title=4.1_The_maximum-subarray_problem C++ での実装です。

int max_sarr(int arr[], int size)
{
    int  max_sum = -9999;
    int sum = 0;
    for(int i = 0; i < size; i++)
    {
        sum += arr[i];
        if(sum > max_sum)
            max_sum = sum;
        if(sum < 0)
            sum = 0;
    }
    return sum;
}
int main()
{
    int arr[] = {10, 4, 2, 12, 16, 1};
    int p = max_sarr(arr, 6);
    cout << p << endl;
    return 0;
}

出力は 45 です。では、私の思考プロセスのどこが間違っているのでしょうか?

4

2 に答える 2

2

sftrabbit の回答は素晴らしいですが、 CLRS ブックの 68 ページのThe Maximum Subarray Problemセクションを強くお勧めします。これは非常に明確であり、漸近的な複雑さと問題の実際の発生についても説明しています。

これに加えて、ご想像のとおり、すべて正の要素を持つ配列であり、その最大部分配列は配列自体になります。

于 2013-04-21T13:32:12.360 に答える