矩陣（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 + ")"); 
} 

}