Lintcode 944. Maximum Submatrix

Given an n x n matrix of positive and negative integers, find the submatrix with the largest possible sum.

Example

Example1

Input:  
matrix = [
    [1,3,-1],
    [2,3,-2],
    [-1,-2,-3]
]
Output: 9
Explanation:
the submatrix with the largest possible sum is:
[
    [1,3],
    [2,3]
]

Example2

Input:  
matrix = [
    [1,1,1],
    [1,1,1],
    [1,1,1]
]
Output: 9
Explanation:
the submatrix with the largest possible sum is:
[
    [1,1,1],
    [1,1,1],
    [1,1,1]
]

Code(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 == null || matrix.length == 0) {
            return 0;
        }
        
        int m = matrix.length;
        int n = matrix[0].length;
        
        int[][] presum = new int[m + 1][n];
        for (int i = 1; i <= m; i++) {
            for (int j = 0; j < n; j++) {
                presum[i][j] = presum[i - 1][j] + matrix[i - 1][j];
            }
        }
        
        int maxSum = 0;
        
        for (int i = 1; i <= m; i++) {
            for (int j = i; j <= m; j++) {
                int curSum = 0;
                int minPreSum = 0;
                for (int k = 0; k < n; k++) {
                    curSum += presum[j][k] - presum[i - 1][k];
                    if (curSum - minPreSum > maxSum) {
                        maxSum = curSum - minPreSum;
                    }
                    minPreSum = Math.min(minPreSum, curSum);
                }
            }
        }
        
        return maxSum;
    }
}