面试题 17.24

Given an NxN 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

Solutions

1. dynamic programming O(mn2)

2. reference: https://leetcode-cn.com/problems/max-submatrix-lcci/solution/zhe-yao-cong-zui-da-zi-xu-he-shuo-qi-you-jian-dao-/

3. Based on solution in problem 53

   • The maximum sum of subarray in a 1d-array can be calculated in O(n) time.

4. For this 2d problem, we iterate over all possible combination of top/bottom(r1, r2) rows in O(n2) time, then given the sum(1d) of each column in this region, we can find the maximum sum of subarrays(c1, c2) which defines a submatrix as matrix[r1:r2][c1:c2].

class Solution {
public:
    vector<int> getMaxMatrix(vector<vector<int>>& matrix) {
        if (!matrix.size()) return {};
        int m = matrix.size(), n = matrix[0].size();
        vector<int> sum(n), rect = {0, 0, 0, 0};
        int res = INT_MIN;

        // for all possible r1:r2
        for (int r1 = 0; r1 < m; r1++) {
            fill(sum.begin(), sum.end(), 0);
            for (int r2 = r1; r2 < m; r2++) {
                int prev = INT_MIN / 2, cur = 0, c1 = 0;
                // use method in problem 53
                for (int c2 = 0; c2 < n; c2++) {
                    sum[c2] += matrix[r2][c2];
                    cur = max(prev + sum[c2], sum[c2]);
                    if (prev < 0)
                        c1 = c2;
                    if (cur > res) {
                        rect = {r1, c1, r2, c2};
                        res = cur;
                    }
                    prev = cur;
                }
            }
        }

        return rect;
    }
};