1
給定一個二維正整數數組,找到總和最大的HxW大小的子矩形。矩形的總和是該矩形中所有元素的總和。2D矩陣內HxW的最大子陣列
輸入: 2D陣列的N×N具有正元素 的子矩形的大小HXW
輸出: HXW大小與它的元件的最大總和的子矩陣。我已經使用強力方法解決了這個問題,但是,我現在正在尋找一個更好的解決方案,它具有更好的複雜性(我的蠻力方法的複雜性是O(n ))。
給定一個二維正整數數組,找到總和最大的HxW大小的子矩形。矩形的總和是該矩形中所有元素的總和。2D矩陣內HxW的最大子陣列
輸入: 2D陣列的N×N具有正元素 的子矩形的大小HXW
輸出: HXW大小與它的元件的最大總和的子矩陣。我已經使用強力方法解決了這個問題,但是,我現在正在尋找一個更好的解決方案,它具有更好的複雜性(我的蠻力方法的複雜性是O(n ))。
首先創建矩陣的累積和:爲O(n 2 )
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)
然後使用兩個循環,您可以將矩形的左上角放在矩陣的每個點上,並計算矩形的總和。
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 2 )。
下面是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)
是不是最大和原來的N×N陣列的子矩形?你說這是所有正整數,所以最大的總和總是將總和原始數組的所有元素。 –
HxW子可重構總是小於原始NxN數組。因此,例如給定一個5x5陣列,找到具有最大元素總和的子陣列尺寸2x2,因此我不能尋找尺寸爲5x5的子陣列,它必須是HxW尺寸,而不是更小,不能更大。 – drakerc