363 Max Sum of Rectangle No Larger Than K

Given a non-empty 2D matrix matrix and an integer k, find the max sum of a rectangle in the matrix such that its sum is no larger than k.

Example:

Given matrix = [
  [1,  0, 1],
  [0, -2, 3]
]
k = 2

The answer is 2. Because the sum of rectangle [[0, 1], [-2, 3]] is 2 and 2 is the max number no larger than k (k = 2).

Note:

• The rectangle inside the matrix must have an area > 0.
• What if the number of rows is much larger than the number of columns?

Solution
kind of "brute-force" solution, using "sub-array sum" idea.

class Solution {
public:
    int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
        int m = matrix.size();
        if ( m == 0 ) return 0;
        int n = matrix[0].size();
        if ( n == 0 ) return 0;
        int res[m][n];
        res[0][0] = matrix[0][0];
        for ( int j = 1; j < n; j++ ) res[0][j] = res[0][j-1] + matrix[0][j];
        for ( int i = 1; i < m; i++ ) {
            int row_sum = 0;
            for ( int j = 0; j < n; j++ ) {
                row_sum += matrix[i][j];
                res[i][j] = res[i-1][j] + row_sum;
            }
        }
        int maxsum = INT_MIN, sum;
        for ( int i = 0; i < m; i++ ) {
            for ( int j = 0; j < n; j++ ) {
                for ( int i1 = -1; i1 < i; i1++ ) {
                    for ( int j1 = -1; j1 < j; j1++ ) {
                        sum = res[i][j];
                        if ( i1 != -1 ) sum -= res[i1][j];
                        if ( j1 != -1 ) sum -= res[i][j1];
                        if ( i1 != -1 and j1 != -1 ) sum += res[i1][j1];
                        if ( sum == k ) return k;
                        if ( sum < k ) maxsum = max(maxsum, sum);
                    }
                }
            }
        }
        return maxsum;
    }
};