2D矩阵中大小为HxW的最大子数组

本文介绍了2D矩阵中大小为HxW的最大子数组的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

给定一个正整数的二维数组，找到具有最大和的大小为HxW的子矩形.矩形的总和是该矩形中所有元素的总和.

Given a 2-dimensional array of positive integers, find the subrectangle of size HxW with the largest sum. The sum of a rectangle is the sum of all the elements in that rectangle.

输入:具有正元素的2D数组NxN子矩形的HxW大小

Input: A 2D array NxN with positive elements The HxW size of the subrectangle

输出:HxW大小的子矩阵，其元素之和最大.

Output: The submatrix of HxW size with the largest sum of its elements.

我已经使用蛮力方法解决了这个问题，但是，我现在正在寻找一种具有更高复杂度的更好的解决方案(我的蛮力方法的复杂度为O(n 6 ))

I've solved this using a brute-force method, however, I'm now looking for a better solution with better complexity (my brute-force method's complexity is O(n6)).

推荐答案

首先创建矩阵的累加和: O(n 2 )

First create the cumulative sum of your matrix: O(n2)

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)是子矩阵(0:i，0:j)中所有元素的总和.您可以使用以下逻辑来计算累积和矩阵:

cumulative_sum(i,j) is the sum of all the elements in the submatrix (0:i,0:j). You can calculate the cumulative sum matrix using below logic:

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)中每个子矩阵的和:

Using the cumulative sum matrix you can calculate sum of every sub-matrix in 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)

然后使用两个循环，可以将 HW 矩形的左上角放在矩阵的每个点上，并计算该矩形的总和.

Then using two loops you can put the top-left of your HW rectangle on every point of the matrix and calculate the sum of that rectangle.

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 )中.

This approach is in O(N2).

这是python实现:

Here is the python implementation:

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)