1000046. Max Submatrix LCCI

难度: Hard

题目描述

Given an NxM matrix of positive and negative integers, write code to find the submatrix with the largest possible sum.

Return an array [r1, c1, r2, c2], where r1, c1 are the row number and the column number of the submatrix's upper left corner respectively, and r2, c2 are the row number of and the column number of lower right corner. If there are more than one answers, return any one of them.

Note: This problem is slightly different from the original one in the book.

Example:

Input:
[
   [-1,0],
   [0,-1]
]
Output: [0,1,0,1]

Note:

• 1 <= matrix.length, matrix[0].length <= 200

解题思路

代码实现

解决方案

java

class Solution {
    public int[] getMaxMatrix(int[][] matrix) {

        int max = Integer.MIN_VALUE;
        int dp = 0;
        int start = 0;
        int[] ans = new int[] { -1, -1, 200, 200 };
        int[] sum = null;

        int m = matrix.length;
        int n = matrix[0].length;
        // 开始行
        for (int i = 0; i < m; i++) {
            sum = new int[n];
            // 结束行
            for (int j = i; j < m; j++) {
                dp = 0;
                start = 0;
                for (int k = 0; k < n; k++) {
                    sum[k] += matrix[j][k];
                    dp += sum[k];
                    if (max < dp) {
                        max = dp;
                        ans = new int[] { i, start, j, k };
                    }
                    if (dp < 0) {
                        dp = 0;
                        start = k + 1;
                    }
                }
            }
        }

        return ans;
    }
}