Maximum Submatrix

• Lintcode : 944 / Leetcode :
• Level : Medium

Problem

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]
]

Concept & Algorithm

筆記

Time Complexity & Space Complexity

time : O(row ^ 2 * col)
space: O(col)

Answer

class Solution {
public:
    int maxSubmatrix(vector<vector<int>> &matrix) {
        if (matrix.size() == 0 || matrix[0].size() == 0) return 0;
        int row = matrix.size(), col = matrix[0].size();
        int maxSum = INT_MIN;
        for (int i = 0; i < row; i++) {
            vector<int> sum(col);
            for (int j = i; j < row; j++) {
                for (int k = 0; k < col; k++) {
                    sum[k] += matrix[j][k];
                }
                int s = findMax(sum);
                maxSum = max(maxSum, s);
            }
        }
        return maxSum;
    }
    int findMax(vector<int> sum) {
        int maxima = sum[0];
        for (int i = 1; i < sum.size(); i++) {
            sum[i] = max(sum[i], sum[i] + sum[i - 1]);
            maxima = max(maxima, sum[i]);
        }
        return maxima;
    }
};

tags: DP

​