algorithm - 2D マトリックス内のサイズ HxW の最大サブアレイ

Question

正の整数の 2 次元配列を指定して、サイズが HxW で合計が最大になる部分四角形を見つけます。長方形の合計は、その長方形内のすべての要素の合計です。

入力: 正の要素を持つ 2D 配列 NxN サブ長方形の HxW サイズ

出力: 要素の合計が最大の HxW サイズの部分行列。

ブルートフォース法を使用してこれを解決しましたが、より複雑なより良いソリューションを探しています (私のブルートフォース法の複雑さは O(n ⁶ ) です)。

Answer 1

最初に行列の累積和を作成します: O(n ² )

Matrix
2 4 5 6
2 3 1 4
2 0 2 1

Cumulative sum
2 6  11 17
4 11 17 27
6 13 21 32

cumulative_sum(i,j)のすべての要素の合計ですsubmatrix (0:i,0:j)。以下のロジックを使用して、累積合計行列を計算できます。

cumulative_sum(i,j) = cumulative_sum(i-1,j) + cumulative_sum(i,j-1) - cumulative_sum(i-1,j-1) + matrix(i,j)

累積合計行列を使用すると、O(1) のすべてのサブ行列の合計を計算できます。

calculating sum of submatrix (r1 ... r2 , c1 ... c2)
sum_sub = cumulative_sum(r2,c2) - cumulative_sum(r1-1,c2) - cumulative_sum(r2,c1-1) + cumulative_sum(r1-1,c1-1)

次に、2 つのループを使用して、 HW四角形の左上をマトリックスのすべての点に配置し、その四角形の合計を計算できます。

for r1=0->n_rows
   for c1=0->n_cols
       r2 = r1 + height - 1
       c2 = c1 + width - 1
       if valid(r1,c1,r2,c2) // doesn't exceed the original matrix
            sum_sub = ... // formula mentioned above
            best = max(sum_sub, best)
return best

このアプローチはO(N ² )にあります。

Python の実装は次のとおりです。

from copy import deepcopy

def findMaxSubmatrix(matrix, height, width):
    nrows = len(matrix)
    ncols = len(matrix[0])           

    cumulative_sum = deepcopy(matrix)

    for r in range(nrows):
        for c in range(ncols):
            if r == 0 and c == 0:
                cumulative_sum[r][c] = matrix[r][c]
            elif r == 0:
                cumulative_sum[r][c] = cumulative_sum[r][c-1] + matrix[r][c]
            elif c == 0:
                cumulative_sum[r][c] = cumulative_sum[r-1][c] + matrix[r][c]
            else:
                cumulative_sum[r][c] = cumulative_sum[r-1][c] + cumulative_sum[r][c-1] - cumulative_sum[r-1][c-1] + matrix[r][c]

    best = 0
    best_pos = None

    for r1 in range(nrows):
        for c1 in range(ncols):
            r2 = r1 + height - 1
            c2 = c1 + width - 1
            if r2 >= nrows or c2 >= ncols:
                continue
            if r1 == 0 and c1 == 0:
                sub_sum = cumulative_sum[r2][c2]
            elif r1 == 0:
                sub_sum = cumulative_sum[r2][c2] - cumulative_sum[r2][c1-1]
            elif c1 == 0:
                sub_sum = cumulative_sum[r2][c2] - cumulative_sum[r1-1][c2]
            else:
                sub_sum = cumulative_sum[r2][c2] - cumulative_sum[r1-1][c2] - cumulative_sum[r2][c1-1] + cumulative_sum[r1-1][c1-1]
            if best < sub_sum:
                best_pos = r1,c1
                best = sub_sum

    print "maximum sum is:", best
    print "top left corner on:", best_pos


matrix = [ [2,4,5,6],
           [2,3,1,4],
           [2,0,2,1] ]
findMaxSubmatrix(matrix,2,2)

出力

maximum sum is: 16
top left corner on: (0, 2)