title: Maximum Submatrix Sum of nxn matrices
body: <p>I'm trying to get the maximum Submatrix Sum from given nxn matrices. From what I read around the algorithm have a complexity of n^3 (kadane). I tried to implement it in java using a code I found here on stackoverflow (written by Anders Gustafsson in C# <a href="https://stackoverflow.com/questions/20113928/how-to-implement-kadane-algorithm-for-2d-matrix">in these post</a>) but it seems to not always work.</p>
  
  <p>my code is this:  </p>
  
  <pre><code>public static void maxSubMatrix(int matrix[][]) {
      // O(n^3) Max Sum Submatrix
  
      int row = matrix.length;
      int col = matrix[0].length; // Get the col-length by taking the length of 
                                  // row 0 (in programm the matrices will be n x n)
  
      // Initialise maxSum
      int maxSum = 0;
  
      // Set left column
      for (int left=0; left&lt;col; left++) {
  
          // Initialise array
          int tempArray[] = new int[row];
  
          // Set right column by left column (outer loop)
          for (int right=left; right&lt;col; right++){
  
              // Calculate sum between current left-right for every row 'i'
              for (int i=0; i&lt;row; i++)
                  tempArray[i] = matrix[i][right];
              // ----
  
              // Find maximum sum in tempArray[]
              int sum = maxSubArray(tempArray);
  
              // Compare sum with maxSum so far, and update it if necessary
              if (sum &gt; maxSum) maxSum = sum;
          }
      }
      System.out.println(maxSum);
  }
  // ==========================
  
  public static int maxSubArray(int array[]){
      // Kadane O(n) Max Sum Subarray
      int maxSum = 0;
      int tempSum = 0;
  
      for (int i=0; i&lt;array.length; i++){
          int b = array[i];
          if (tempSum + b &gt; 0) tempSum += b;
          else tempSum = 0;
          maxSum = Math.max(maxSum, tempSum);
      }
      return maxSum;
  }
  </code></pre>
  
  <p>I have three examples:  </p>
  
  <p>Matrix 1<br>
  -2 -3<br>
  -1 -4<br>
  Output is 0 (Also the empty 0x0 Matrix is a solution)  </p>
  
  <p>Matrix 2<br>
  2 -1<br>
  -2 -1<br>
  Output is 2    </p>
  
  <p>Matrix 3<br>
  -1 3<br>
  3 -1<br>
  Output is 3, but should be 4</p>
  
  <p>Maybe someone can see the error. I'm also open to completely new idea to implement it.</p>