[解決済み] 最大和サブアレイのブルートフォースはなぜO(n^2)なのか？

質問

は サブアレイの最大和 は、コンピュータサイエンスで有名な問題です。

少なくとも2つの解がある。

1. ブルートフォース、可能なすべての部分配列を見つけ、最大値を求める。
2. のバリエーションを使用します。 Karanes アルゴリズム を使用して、配列の最初のパスを通過する間に、グローバルな最大値を計算します。

動画で見る チュートリアル 筆者は、ブルートフォース方式は O(n^2) を読むことです。 別解 一人思う O(n^2) であり、別の人は O(n^3)

ブルートフォースは O(n^2) または O(n^3) ? さらに重要なことは、ブルートフォースメソッドに対してどのような分析を行ったか、そしてそれが O(?) ?

解決方法は？

まあ、どの程度の強引さかにもよりますが。

をすべて生成すると (i, j): i <= j のペアを作り、その間の和を計算すると、それは O(n^3) :

....
for (int i = 0; i < n; i++)
    for (int j = i; j < n; j++) {
        int sum = 0;
        for (int k = i; k <= j; k++)
            sum += a[k];
        if (sum > max)
            max = sum;
    }

すべての位置からスタートしてランニングサム（総和）を計算すると O(n^2) :

....
for(int i = 0; i < n; i++) {
    int sum = 0;
    for (int j = i; j < n; j++) {
        sum += a[j];
        if (sum > max)
            max = sum;
    }
}