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):

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

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;     } }