Maximum Submatrix

Java

public class Solution {
    /**
     * @param matrix: the given matrix
     * @return: the largest possible sum
     */
    public int maxSubmatrix(int[][] matrix) {
        // write your code here
        if(matrix.length == 0 || matrix[0].length == 0){
            return 0;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] sum = new int[m+1][n+1];
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                sum[i][j] = sum[i-1][j] + matrix[i-1][j-1];
            }
        }
        int max = Integer.MIN_VALUE;
        for(int i = 0; i <= m; i++){
            for(int j = i+1; j <= m; j++){
                int cur = 0;
                for(int k = 1; k <= n; k++){
                    cur += (sum[j][k] - sum[i][k]);
                    max = Math.max(cur, max);
                    cur = Math.max(0, cur);
                }
            }
        }
        return max;
    }
}