行列（2D）のサブ矩形の最大和

Question

行列内のサブ矩形の最大和を求める問題を解決しようとしています。今のところ私はアルゴリズムの約90％を実装することができました。 （私が話していることを知らない人のために：https://www.youtube.com/watch?v=yCQN096CwWM）

私の問題は、負の場合、私の一時配列のトップまたはボトム値を削除する方法がわかりません。削除された負の値がどのインデックスからカミングしていたかを知る方法はもちろん。

私はこのような1次元（1D）で問題を解決した

：私はここまで得ている2次元（2D）で

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); 

：

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

}