得到最大和的子矩阵？
得到最大和的子矩阵？
提问于 2010-04-15 16:55:04
Input：具有正负元素的二维数组矩阵- NxN。
输出矩阵(Output)：任意大小的子矩阵，其和是所有可能的子矩阵中的最大值。
Requirement：算法复杂度为O(N^3)
历史：在算法专家Larry和对Kadane算法的修改的帮助下，我成功地解决了部分求和的问题，这是的一部分，下面是Java语言。
多亏了Ruby ，他成功地解决了剩下的问题，即确定矩阵的边界，即Ruby语言的左上角、右下角。
回答 11
Stack Overflow用户
回答已采纳
发布于 2011-02-18 01:14:52
关于恢复实际的子矩阵，而不仅仅是最大和，这是我得到的。很抱歉，我没有时间将我的代码翻译成您的java版本，所以我在这里发布了我的Ruby代码，并在关键部分添加了一些注释
def max_contiguous_submatrix_n3(m)
rows = m.count
cols = rows ? m.first.count : 0
vps = Array.new(rows)
for i in 0..rows
vps[i] = Array.new(cols, 0)
end
for j in 0...cols
vps[0][j] = m[0][j]
for i in 1...rows
vps[i][j] = vps[i-1][j] + m[i][j]
end
end
max = [m[0][0],0,0,0,0] # this is the result, stores [max,top,left,bottom,right]
# these arrays are used over Kadane
sum = Array.new(cols) # obvious sum array used in Kadane
pos = Array.new(cols) # keeps track of the beginning position for the max subseq ending in j
for i in 0...rows
for k in i...rows
# Kadane over all columns with the i..k rows
sum.fill(0) # clean both the sum and pos arrays for the upcoming Kadane
pos.fill(0)
local_max = 0 # we keep track of the position of the max value over each Kadane's execution
# notice that we do not keep track of the max value, but only its position
sum[0] = vps[k][0] - (i==0 ? 0 : vps[i-1][0])
for j in 1...cols
value = vps[k][j] - (i==0 ? 0 : vps[i-1][j])
if sum[j-1] > 0
sum[j] = sum[j-1] + value
pos[j] = pos[j-1]
else
sum[j] = value
pos[j] = j
end
if sum[j] > sum[local_max]
local_max = j
end
end
# Kadane ends here
# Here's the key thing
# If the max value obtained over the past Kadane's execution is larger than
# the current maximum, then update the max array with sum and bounds
if sum[local_max] > max[0]
# sum[local_max] is the new max value
# the corresponding submatrix goes from rows i..k.
# and from columns pos[local_max]..local_max
# the array below contains [max_sum,top,left,bottom,right]
max = [sum[local_max], i, pos[local_max], k, local_max]
end
end
end
return max # return the array with [max_sum,top,left,bottom,right]
end需要澄清的一些注意事项：
为了方便起见，我使用数组来存储与结果相关的所有值。你可以只使用5个独立变量: max，top，left，bottom，right。只需在一行中向数组赋值，然后子例程返回包含所有所需信息的数组就更容易了。
如果您将这段代码复制并粘贴到支持Ruby的文本突出显示编辑器中，您显然会更好地理解它。希望这能有所帮助！
Stack Overflow用户
发布于 2013-08-14 06:49:52
下面是与发布的代码一起使用的解释。有两个关键技巧可以有效地使其工作：(I) Kadane算法和(II)使用前缀和。您还需要(III)将技巧应用于矩阵。
第一部分:卡丹算法
Kadane的算法是一种寻找具有最大和的邻接子序列的方法。让我们从寻找最大邻接子序列的强力方法开始，然后考虑对其进行优化，以获得Kadane算法。
假设你有这样的序列：
-1, 2, 3, -2对于蛮力方法，沿着生成所有可能的子序列的序列走，如下所示。考虑到所有的可能性，我们可以在每个步骤中开始、扩展或结束一个列表。
At index 0, we consider appending the -1
-1, 2, 3, -2
^
Possible subsequences:
-1 [sum -1]
At index 1, we consider appending the 2
-1, 2, 3, -2
^
Possible subsequences:
-1 (end) [sum -1]
-1, 2 [sum 1]
2 [sum 2]
At index 2, we consider appending the 3
-1, 2, 3, -2
^
Possible subsequences:
-1, (end) [sum -1]
-1, 2 (end) [sum -1]
2 (end) [sum 2]
-1, 2, 3 [sum 4]
2, 3 [sum 5]
3 [sum 3]
At index 3, we consider appending the -2
-1, 2, 3, -2
^
Possible subsequences:
-1, (end) [sum -1]
-1, 2 (end) [sum 1]
2 (end) [sum 2]
-1, 2 3 (end) [sum 4]
2, 3 (end) [sum 5]
3, (end) [sum 3]
-1, 2, 3, -2 [sum 2]
2, 3, -2 [sum 3]
3, -2 [sum 1]
-2 [sum -2]对于这种蛮力方法，我们最终选择了具有最佳和的列表(2, 3)，这就是答案。然而，为了提高效率，考虑到您真的不需要保留每个列表。在尚未结束的列表中，您只需要保留最好的列表，其他列表不能做得更好。在已经结束的列表中，您可能只需要保留最好的列表，而且只有在它比未结束的列表更好的情况下才需要。
因此，您只需使用一个位置数组和一个和数组就可以跟踪所需的内容。位置数组的定义如下：position[r] = s跟踪以r结尾并以s开头的列表。并且，对于以index r结尾的子序列，sum[r]会给出一个和。这是一种优化的方法，即Kadane算法。
再次运行示例，以这种方式跟踪我们的进度：
At index 0, we consider appending the -1
-1, 2, 3, -2
^
We start a new subsequence for the first element.
position[0] = 0
sum[0] = -1
At index 1, we consider appending the 2
-1, 2, 3, -2
^
We choose to start a new subsequence because that gives a higher sum than extending.
position[0] = 0 sum[0] = -1
position[1] = 1 sum[1] = 2
At index 2, we consider appending the 3
-1, 2, 3, -2
^
We choose to extend a subsequence because that gives a higher sum than starting a new one.
position[0] = 0 sum[0] = -1
position[1] = 1 sum[1] = 2
position[2] = 1 sum[2] = 5
Again, we choose to extend because that gives a higher sum that starting a new one.
-1, 2, 3, -2
^
position[0] = 0 sum[0] = -1
position[1] = 1 sum[1] = 2
position[2] = 1 sum[2] = 5
positions[3] = 3 sum[3] = 3同样，最佳和是5，列表是从索引1到索引2，即(2，3)。
第二部分:前缀和
我们想要有一种方法来计算沿着一行的和，对于任何起点到任何终点。我希望在O(1)时间内计算该和，而不仅仅是加法，这需要O(m)时间，其中m是和中元素的数量。通过一些预计算，这是可以实现的。下面是如何实现的。假设你有一个矩阵：
a d g
b e h
c f i你可以预先计算这个矩阵：
a d g
a+b d+e g+h
a+b+c d+e+f g+h+i完成后，只需减去两个值，就可以得到从列中的任何开始到结束的任何列的总和。
第三部分:将各种技巧结合起来，以求最大子矩阵
假设您知道最大子矩阵的顶行和底行。你可以这样做：
- 忽略顶部行以上的行和底部行下面的行。
- 对于剩余的矩阵，考虑使用每列的和来形成一个序列(有点像代表多行的行)。(您可以使用前缀sums approach.)
- Use Kadane的方法快速计算此序列中的任何元素，以找出此序列中的最佳子序列。你得到的索引会告诉你最优子矩阵的左右位置。
现在，如何真正计算出顶行和底行？试一试所有的可能性。试着把顶部放在你能放的任何地方，把底部放在你能放的任何地方，并运行前面描述的Kadane-base过程。当你找到一个最大值时，你可以跟踪顶部和底部的位置。
查找行和列需要O(M^2)，其中M是行数。查找列需要O(N)时间，其中N是列数。所以总时间是O(M^2 * N)。如果为M=N，则所需时间为O(N^3)。
Stack Overflow用户
发布于 2013-06-06 09:42:56
答案已经很多了，但这里是我编写的另一个Java实现。它比较了3种解决方案：
- Na(蛮力)- O(n^6) time
- 明显的DP解- O(n^4) time
- O(n^3) space
- 基于卡丹算法的更巧妙的DP解- O(n^3) time
- O(n^2) space
有n= 10到n= 70的示例运行，增量为10，比较了运行时间和空间需求。
代码：
public class MaxSubarray2D {
static int LENGTH;
final static int MAX_VAL = 10;
public static void main(String[] args) {
for (int i = 10; i <= 70; i += 10) {
LENGTH = i;
int[][] a = new int[LENGTH][LENGTH];
for (int row = 0; row < LENGTH; row++) {
for (int col = 0; col < LENGTH; col++) {
a[row][col] = (int) (Math.random() * (MAX_VAL + 1));
if (Math.random() > 0.5D) {
a[row][col] = -a[row][col];
}
//System.out.printf("%4d", a[row][col]);
}
//System.out.println();
}
System.out.println("N = " + LENGTH);
System.out.println("-------");
long start, end;
start = System.currentTimeMillis();
naiveSolution(a);
end = System.currentTimeMillis();
System.out.println(" run time: " + (end - start) + " ms no auxiliary space requirements");
start = System.currentTimeMillis();
dynamicProgammingSolution(a);
end = System.currentTimeMillis();
System.out.println(" run time: " + (end - start) + " ms requires auxiliary space for "
+ ((int) Math.pow(LENGTH, 4)) + " integers");
start = System.currentTimeMillis();
kadane2D(a);
end = System.currentTimeMillis();
System.out.println(" run time: " + (end - start) + " ms requires auxiliary space for " +
+ ((int) Math.pow(LENGTH, 2)) + " integers");
System.out.println();
System.out.println();
}
}
// O(N^2) !!!
public static void kadane2D(int[][] a) {
int[][] s = new int[LENGTH + 1][LENGTH]; // [ending row][sum from row zero to ending row] (rows 1-indexed!)
for (int r = 0; r < LENGTH + 1; r++) {
for (int c = 0; c < LENGTH; c++) {
s[r][c] = 0;
}
}
for (int r = 1; r < LENGTH + 1; r++) {
for (int c = 0; c < LENGTH; c++) {
s[r][c] = s[r - 1][c] + a[r - 1][c];
}
}
int maxSum = Integer.MIN_VALUE;
int maxRowStart = -1;
int maxColStart = -1;
int maxRowEnd = -1;
int maxColEnd = -1;
for (int r1 = 1; r1 < LENGTH + 1; r1++) { // rows 1-indexed!
for (int r2 = r1; r2 < LENGTH + 1; r2++) { // rows 1-indexed!
int[] s1 = new int[LENGTH];
for (int c = 0; c < LENGTH; c++) {
s1[c] = s[r2][c] - s[r1 - 1][c];
}
int max = 0;
int c1 = 0;
for (int c = 0; c < LENGTH; c++) {
max = s1[c] + max;
if (max <= 0) {
max = 0;
c1 = c + 1;
}
if (max > maxSum) {
maxSum = max;
maxRowStart = r1 - 1;
maxColStart = c1;
maxRowEnd = r2 - 1;
maxColEnd = c;
}
}
}
}
System.out.print("KADANE SOLUTION | Max sum: " + maxSum);
System.out.print(" Start: (" + maxRowStart + ", " + maxColStart +
") End: (" + maxRowEnd + ", " + maxColEnd + ")");
}
// O(N^4) !!!
public static void dynamicProgammingSolution(int[][] a) {
int[][][][] dynTable = new int[LENGTH][LENGTH][LENGTH + 1][LENGTH + 1]; // [row][col][height][width]
int maxSum = Integer.MIN_VALUE;
int maxRowStart = -1;
int maxColStart = -1;
int maxRowEnd = -1;
int maxColEnd = -1;
for (int r = 0; r < LENGTH; r++) {
for (int c = 0; c < LENGTH; c++) {
for (int h = 0; h < LENGTH + 1; h++) {
for (int w = 0; w < LENGTH + 1; w++) {
dynTable[r][c][h][w] = 0;
}
}
}
}
for (int r = 0; r < LENGTH; r++) {
for (int c = 0; c < LENGTH; c++) {
for (int h = 1; h <= LENGTH - r; h++) {
int rowTotal = 0;
for (int w = 1; w <= LENGTH - c; w++) {
rowTotal += a[r + h - 1][c + w - 1];
dynTable[r][c][h][w] = rowTotal + dynTable[r][c][h - 1][w];
}
}
}
}
for (int r = 0; r < LENGTH; r++) {
for (int c = 0; c < LENGTH; c++) {
for (int h = 0; h < LENGTH + 1; h++) {
for (int w = 0; w < LENGTH + 1; w++) {
if (dynTable[r][c][h][w] > maxSum) {
maxSum = dynTable[r][c][h][w];
maxRowStart = r;
maxColStart = c;
maxRowEnd = r + h - 1;
maxColEnd = c + w - 1;
}
}
}
}
}
System.out.print(" DP SOLUTION | Max sum: " + maxSum);
System.out.print(" Start: (" + maxRowStart + ", " + maxColStart +
") End: (" + maxRowEnd + ", " + maxColEnd + ")");
}
// O(N^6) !!!
public static void naiveSolution(int[][] a) {
int maxSum = Integer.MIN_VALUE;
int maxRowStart = -1;
int maxColStart = -1;
int maxRowEnd = -1;
int maxColEnd = -1;
for (int rowStart = 0; rowStart < LENGTH; rowStart++) {
for (int colStart = 0; colStart < LENGTH; colStart++) {
for (int rowEnd = 0; rowEnd < LENGTH; rowEnd++) {
for (int colEnd = 0; colEnd < LENGTH; colEnd++) {
int sum = 0;
for (int row = rowStart; row <= rowEnd; row++) {
for (int col = colStart; col <= colEnd; col++) {
sum += a[row][col];
}
}
if (sum > maxSum) {
maxSum = sum;
maxRowStart = rowStart;
maxColStart = colStart;
maxRowEnd = rowEnd;
maxColEnd = colEnd;
}
}
}
}
}
System.out.print(" NAIVE SOLUTION | Max sum: " + maxSum);
System.out.print(" Start: (" + maxRowStart + ", " + maxColStart +
") End: (" + maxRowEnd + ", " + maxColEnd + ")");
}
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/2643908
复制相关文章
相似问题
腾讯云开发者
