2D行列内のサイズHxWの最大サブアレイ

Question

正の整数の2次元配列が与えられた場合、最大の合計を持つサイズHxWの部分矩形を見つける。矩形の合計は、その矩形内のすべての要素の合計です。

入力：その要素の最大の和を有するHxWサイズの 部分行列： A 2D配列N×Nの正の要素 subrectangle

出力のHxWサイズを有します。

私はbrute-forceメソッドを使ってこの問題を解決しましたが、私は現在、より優れた複雑さでより良いソリューションを探しています（私のブルートフォースメソッドの複雑さは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)のすべての要素の合計です。 あなたは、論理の下に使用して累積和行列を計算することができます：あなたはO内のすべてのサブ行列の合計を計算することができ累積和行列を使用して

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

（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)