1

私は現在、Jon Bentley の "Programming Pearls" を読んでいますが、その中には私には答えられないような質問があります。ここにあります：

最大部分配列の問題では、実数の nxn 配列が与えられ、長方形の部分配列に含まれる最大和を見つけなければなりません。

この章では、配列の最大値を見つけるためのアルゴリズムをリストしています:
maxsofar = 0
maxendinghere = 0
for i = [0, n) // n) = n-1
/*ivariant: maxendinghere と maxsofar は x[ に対して正確です。 0…i-1] */
maxendinghere = mac(maxendinghere + x[i], 0)
maxsofar = mac(maxsofar, maxendinghere)

上記のアルゴリズム のすべての行のすべての列
の行に沿って何かを言うことができるかどうかを検討しています

しかし、それがうまくいくかどうかはわかりません。何か案は？

4

1 に答える 1

2

まず第一に、1 次元配列のバージョン (1 次元配列の最大連続和) を理解する必要があります。

1次元配列バージョンを解くには、アルゴリズムは簡単で、上記で説明しました。

maxsofar = 0
maxendinghere = 0
for i = [0, n)
    maxendinghere = max(maxendinghere + x[i], 0)
    maxsofar = max(maxsofar, maxendinghere)

これは O(n) です。次に、2d バージョンに拡張できます。2D バージョンの場合、それを 1D バージョンに変換しても上記のアルゴリズムを使用できますが、どうすればよいでしょうか? 1 つの列の値を合計し、その合計を新しい 1 次元配列として扱います。例：

行列は次のように 2*2 です。

1 2
3 4

合計した後、あなたは得ることができます

4 6

とった？i 番目の行から j 番目の行までの列の合計を計算するすべての可能な方法を列挙するだけです。次に、上記の鍵アルゴリズムを適用します。疑似コード:

for i=0 to n
    for j=i to n
        create a new array which contains the column sum from the ith row to jth row
        apply the above O(n) algorithm to get the maximum

総複雑度は O(n^3)

于 2013-02-06T01:33:53.180 に答える