矩阵（2D）中的子矩形的最大总和

Question

我试图解决找到矩阵中的子矩形的最大总和的问题。到目前为止，我已经实现了大约90％的算法。 （对于你们谁不知道我在说什么：https://www.youtube.com/watch?v=yCQN096CwWM）

我的问题是，我不知道如何删除我的临时数组的顶部或底部值，如果他们是负面的。更何况如何知道删除的负值是从哪个索引中扣除的。

我曾在一维（1D）解决了这个问题是这样的：

int maxSoFar = 0; 
int maxEndingHere = 0; 
    int i; 
    for (i = 0; i < input.length; i++) { 
     System.out.println(i + " + " + input[i]); 
     if (maxEndingHere + input[i] > 0) { 
      maxEndingHere += input[i]; 
     } else { 
      maxEndingHere = 0; 
     } 
     if (maxSoFar < maxEndingHere) { 
      maxSoFar = maxEndingHere; 
     } 
    } 
    System.out.println(maxSoFar); 

在二维（2D）我有这个迄今为止得到：

int[][] input = new int[4][5]; 
    input[0][0] = 2; 
    input[0][1] = 1; 
    input[0][2] = -3; 
    input[0][3] = -4; 
    input[0][4] = 5; 
    input[1][0] = 0; 
    input[1][1] = 6; 
    input[1][2] = 3; 
    input[1][3] = 4; 
    input[1][4] = 1; 
    input[2][0] = 2; 
    input[2][1] = -2; 
    input[2][2] = -1; 
    input[2][3] = 4; 
    input[2][4] = -5; 
    input[3][0] = -3; 
    input[3][1] = 3; 
    input[3][2] = 1; 
    input[3][3] = 0; 
    input[3][4] = 3; 
    int currentSum = 0; 
    int maxSum = 0; 
    int L; 
    int R; 
    int maxR = 0; 
    int maxL = 0; 
    int maxUp = 0; 
    int maxDown = 0; 
    int k; 
    int j; 
    int[][] temp = new int[4][1]; 

    for (L = 0; L < input.length; L++) { 
     temp[0][0] = 0; 
     temp[1][0] = 0; 
     temp[2][0] = 0; 
     temp[3][0] = 0; 
     for (R = L; R < input[0].length; R++) { 
      currentSum = 0; 
      for (k = 0; k < temp.length; k++) { 
       temp[k][0] += input[k][R]; 
       if (currentSum + input[k][R]<0){ 
        currentSum += input[k][R]; 
       } 
       else {currentSum = 0;} 
       if (k == 3 && currentSum >= maxSum) { 
        maxSum = currentSum; 
        maxR = R; 
        maxL = L; 
       } 
      } 
     } 
    } 
    System.out.println("Max sum = " + maxSum); 
    System.out.println("Max R = " + maxR); 
    System.out.println("Max L = " + maxL); 

这是我的第一篇文章在这里，所以请让我知道如果我失去了一些东西或类似的东西。

谢谢你的帮助！

Answer 1

我设法解决这个问题，这里是工作代码：

（我不知道为什么我有一个downvote，请解释一下，所以我能避免犯同样的错误在未来）

import java.util.Arrays; 
public class Algoritme4 { 
public static void main(String[] args) { 
    algo2D(new int[][]{ 
      {2, 1, -3, -4, 5}, 
      {0, 6, 3, 4, 1}, 
      {2, -2, -1, 4, -5}, 
      {-3, 3, 1, 0, 3} 
    }); 
} 

private static int[] algo4(int[] a) { 
    int maxEndingHere = 0; 
    int i; 
    int[] result = {0, 0, 0}; 
    for (i = 0; i < a.length; i++) { 
     if (maxEndingHere + a[i] > 0) { 
      maxEndingHere += a[i]; 
     } else { 
      maxEndingHere = 0; 
      result[1] = i + 1; 
     } 
     if (result[0] < maxEndingHere) { 
      result[0] = maxEndingHere; 
      result[2] = i; 
     } 
    } 
    System.out.println("Max sum of sub matrix = " + result[0] + " (" + result[1] + "," + result[2] + ")"); 
    return result; 
} 
private static void algo2D(int[][] a){ 
    int[] result = {0,0,0}; 
    int maxSoFar = 0; 
    int maxR = 0; 
    int maxL = 0; 
    int start = 0; 
    int slut = 0; 
    int L; 
    int R; 
    int k; 

    for (L = 0; L<a.length; L++) { 
     int[] temp = {0,0,0,0}; 
     for (R = L; R < a[0].length; R++){ 
      System.out.println("R = " + R); 
      System.out.println("L = " + L); 
      for (k = 0; k < a.length; k++) { 
       temp[k] += a[k][R]; 
       if (k==3) { 
        System.out.println("temp = " + Arrays.toString(temp)); 
        result = algo4(temp); 
       } 
       if (result[0]> maxSoFar){ 
        maxSoFar = result[0]; 
        maxL = L; 
        maxR = R; 
        start = result[1]; 
        slut = result[2]; 
       } 

      } 

     } 
    } 
    System.out.println("Max: " + maxSoFar + " (" + maxL + "," + start + ") (" + maxR + "," + slut + ")"); 
} 

}