Getting the submatrix with maximum sum?

Question

Input: A 2-dimensional array NxN - Matrix - with positive and negative elements.

Output: A submatrix of any size such that its summation is the maximum among all possible submatrices.

Requirement: Algorithm complexity to be of O(N^3)

History: With the help of the Algorithmist, Larry and a modification of Kadane's Algorithm, i managed to solve the problem partly which is determining the summation only - below in Java.
Thanks to Ernesto who managed to solve the rest of the problem which is determining the boundaries of the matrix i.e. top-left, bottom-right corners - below in Ruby.

Answer 1

About recovering the actual submatrix, and not just the maximum sum, here's what I got. Sorry I do not have time to translate my code to your java version, so I'm posting my Ruby code with some comments in the key parts

def max_contiguous_submatrix_n3(m)
  rows = m.count
  cols = rows ? m.first.count : 0

  vps = Array.new(rows)
  for i in 0..rows
    vps[i] = Array.new(cols, 0)
  end

  for j in 0...cols
    vps[0][j] = m[0][j]
    for i in 1...rows
      vps[i][j] = vps[i-1][j] + m[i][j]
    end
  end

  max = [m[0][0],0,0,0,0] # this is the result, stores [max,top,left,bottom,right]
  # these arrays are used over Kadane
  sum = Array.new(cols) # obvious sum array used in Kadane
  pos = Array.new(cols) # keeps track of the beginning position for the max subseq ending in j

  for i in 0...rows
    for k in i...rows
      # Kadane over all columns with the i..k rows
      sum.fill(0) # clean both the sum and pos arrays for the upcoming Kadane
      pos.fill(0)
      local_max = 0 # we keep track of the position of the max value over each Kadane's execution
      # notice that we do not keep track of the max value, but only its position
      sum[0] = vps[k][0] - (i==0 ? 0 : vps[i-1][0])
      for j in 1...cols
        value = vps[k][j] - (i==0 ? 0 : vps[i-1][j])
        if sum[j-1] > 0
          sum[j] = sum[j-1] + value
          pos[j] = pos[j-1]
        else
          sum[j] = value
          pos[j] = j
        end
        if sum[j] > sum[local_max]
          local_max = j
        end
      end
      # Kadane ends here

      # Here's the key thing
      # If the max value obtained over the past Kadane's execution is larger than
      # the current maximum, then update the max array with sum and bounds
      if sum[local_max] > max[0]
        # sum[local_max] is the new max value
        # the corresponding submatrix goes from rows i..k.
        # and from columns pos[local_max]..local_max
        # the array below contains [max_sum,top,left,bottom,right]
        max = [sum[local_max], i, pos[local_max], k, local_max]
      end
    end
  end

  return max # return the array with [max_sum,top,left,bottom,right]
end

Some notes for clarification:

I use an array to store all the values pertaining to the result for convenience. You can just use five standalone variables: max, top, left, bottom, right. It's just easier to assign in one line to the array and then the subroutine returns the array with all the needed information.

If you copy and paste this code in a text-highlight-enabled editor with Ruby support you'll obviously understand it better. Hope this helps!