我有一个包含各种数据点的二维数组参考图1。
我需要把它分成4个象限，这样每个象限内所有点的总和就最小化了。每个象限的最小大小是4x4，它可以更大但不能更小，也不一定是正方形。例如，最佳象限的大小可以是5x3。
我需要找到最佳的索引x和y，这将导致象限内的最小和。
我认为是重量分配问题。我可以把2d数组中的所有值相加，得到sum，s，现在我需要把sum，s平均分布在4个象限上。我知道我已经提到了每个象限的和必须是最小可能的，但它更像是平衡最小值。
最佳答案
您可以使用Summed Area Table有效地对每个象限中的值求和这是一个与矩阵具有相同维度的矩阵，其中table[i][j]是原始矩阵中从第0行到第i行和第0列到第j列的所有元素的总和。
您可以这样计算（伪代码）：
for i = 0 to rows
row_sum = 0
for j = 0 to columns
row_sum += matrix[i][j]
table[i][j] = row_sum
if i > 0
table[i][j] += table[i-1][j]
上面的代码在每一行上保持一个运行和，并将其添加到同一列上一行的表条目中。
然后，可以使用此表计算给定拆分的每个象限的值。假设要在第i行之后水平拆分为象限，在第j列之后垂直拆分为象限，象限如下：
a | b
--+--
c | d
可以这样计算象限和：
a = table[i][j]
b = table[i][columns-1] - a
c = table[rows-1][j] - a
d = table[rows-1][columns-1] - (a + b + c)
因此，您可以迭代矩阵，并使用4个表查找和一些简单的加减运算来计算每个可能的拆分位置的象限之和跟踪最理想的（根据你的标准，例如最小象限和最大象限之间的最小差异），这就是你的答案。
矩阵中元素的个数是o（n）。