2D range sum, Kadane’s algorithm and maximum subarray sum no more than k

363. Max Sum of Rectangle No Larger Than K

2D range sum based

We can use brute force solution with 2D range sum.

The complexity is O(row ^ 2 * col ^ 2)

int cusum[200][200];
class Solution {
public:
    int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
        const int m = matrix.size(), n = matrix[0].size();
        //using vector will get TLE
        //vector<vector<int>> cusum(m + 1, vector<int>(n + 1, 0));
        memset(cusum, 0, sizeof cusum);
        for (int i = 1; i <= m; ++i)
            for (int j = 1; j <= n; ++j)
                cusum[i][j] = cusum[i-1][j] + cusum[i][j-1] - cusum[i-1][j-1] + matrix[i-1][j-1];
        int ret = INT_MIN, thisret = 0;
         for (int i = 1; i <= m; ++i)
            for (int j = 1; j <= n; ++j)
                for (int r = i; r <= m; ++r)
                    for (int c = j; c <= n; ++c){
                        thisret = cusum[r][c] - cusum[i-1][c] - cusum[r][j-1] + cusum[i-1][j-1];
                        if (thisret <= k) ret = max(ret, thisret); 
                    }
        return ret;
    }
};

An improved version based on [1]

We are going to use 2D Kadane’s algorithm and set to solve this problem.

// O(ROW^2 * COL * log COL)
class Solution {
public:
    int max_no_larger_k(vector<int> colPrefix, int k) {
        // https://www.quora.com/Given-an-array-of-integers-A-and-an-integer-k-find-a-subarray-that-contains-the-largest-sum-subject-to-a-constraint-that-the-sum-is-less-than-k
        // O(COL log COL)
        set<int> s;
        int ret = INT_MIN, cusum = 0;
        s.insert(cusum);  s.insert(cusum);
        for (auto & x: colPrefix){
            cusum += x;
            // cusum - cusum_old <= k
            // cusum_old >= cusum - k
            int cusum_old = cusum - k;
            auto it = s.lower_bound(cusum_old);
            if (it != s.end()) ret = max(ret, cusum - (*it));
            s.insert(cusum);
        }
        return ret;
    }
    int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
        const int ROW = matrix.size(), COL = matrix[0].size();
        // the prefix sum per col from row1 to row2
        int ret = INT_MIN;
        // reference https://www.youtube.com/watch?v=yCQN096CwWM
        // solve it along the row instead of along the column
        // O(ROW^2 * COL)
        for (int row1 = 0; row1 <  ROW; ++ row1){
            vector<int> row1ToRow2_ColPrefix(COL, 0);
            for (int row2 = row1; row2 < ROW; ++ row2){
                // update the column direction prefixsum
                for (int j = 0; j < COL; ++j)row1ToRow2_ColPrefix[j] += matrix[row2][j]; 
                int thisret = max_no_larger_k(row1ToRow2_ColPrefix, k);
                ret = max(ret, thisret);
            }
        }
        return ret;
    }
};

Reference

[1] https://leetcode.com/problems/max-sum-of-rectangle-no-larger-than-k/discuss/83599/Accepted-C%2B%2B-codes-with-explanation-and-references

[2]https://www.youtube.com/watch?v=yCQN096CwWM

[3] https://www.quora.com/Given-an-array-of-integers-A-and-an-integer-k-find-a-subarray-that-contains-the-largest-sum-subject-to-a-constraint-that-the-sum-is-less-than-k