Sub-matrix with largest sum

Given an NxN matrix of positive and negative integers, write code to find the sub-matrix with the largest possible sum 

Cracking the coding interview provides an O(n^4) solution, which I really don't like. I was trying to use the maximum Subarray method, which was on the right track, but I missed a key point: I need to add up all previous subarrays.

The official name of calculating the maximum subarray is called the Kadane's algorithm. To extend it to get the maximum sub matrix in a 2D matrix, we first fix the left and right point (column index), then we calculate the accumulate sum from left to right for each row, and calculate the maximum subarray using Kadane's algorithm for the tmpSum array. Since we need to check all left and right bound, these two operations will take O(n^2), calculating the maximum subarray will take another O(n), so overall is O(n^3).

public class LargestSubMatrix {
 static int upperLeft = 0;
 static int upperRight = 0;
 static int length = 0;
 static int maxSum = Integer.MIN_VALUE;
 public static int largestArea(int[][] matrix){
  if(matrix == null || matrix.length == 0 || matrix[0].length == 0)
   return 0;
  int m = matrix.length;
  int n = matrix[0].length;
  int[] tmp = new int[m];
  for(int left = 0; left < n; left++){
   Arrays.fill(tmp, 0);
   for(int right = left; right < n; right++){
    for(int i = 0; i < m; i++)
     tmp[i] += matrix[i][right];
    int sum = maxSubArray(tmp);
    int tmpLength = length;
    if(sum > maxSum){
     maxSum = sum;
     upperLeft = left;
     upperRight = right;
    }
    else
     length = tmpLength;
   }
  }
  return maxSum;
 }
 private static int maxSubArray(int[] tmp){
  int tmpStart = 0;
  int sum = 0;
  int start = 0, finish = -1;
  int max = Integer.MIN_VALUE;
  for(int i = 0; i < tmp.length; i++){
   sum += tmp[i];
   if(sum < 0){
    sum = 0;
    tmpStart = i + 1;
   } else if(sum > max){
    max = sum;
    start = tmpStart;
    finish = i;
   }
  }
  if(finish != -1){
   if(max > maxSum)
    length = finish - start + 1;
   return max;
  }
  max = tmp[0];
  length = 1;
  for(int i = 1; i < tmp.length; i++)
   max = Math.max(max, tmp[i]);
  return max;
 }

 public static void main(String[] args) {
  int[][] matrix = new int[4][5];
  matrix[0][0] = 1;
  matrix[0][1] = 2;
  matrix[0][2] = -1;
  matrix[0][3] = -4;
  matrix[0][4] = -20;
  matrix[1][0] = -8;
  matrix[1][1] = -3;
  matrix[1][2] = 4;
  matrix[1][3] = 2;
  matrix[1][4] = 1;
  matrix[2][0] = 3;
  matrix[2][1] = 8;
  matrix[2][2] = 10;
  matrix[2][3] = 1;
  matrix[2][4] = 3;
  matrix[3][0] = -4;
  matrix[3][1] = -1;
  matrix[3][2] = 1;
  matrix[3][3] = 7;
  matrix[3][4] = -6;
  
  System.out.println(largestArea(matrix));
  System.out.println(upperLeft);
  System.out.println(upperRight);
  System.out.println(length);

 }

}