363.Max Sum of Rectangle No Larger Than K¶

363.Max Sum of Rectangle No Larger Than K¶

Tags: Hard Dynamic Programming Queue

Company: Google

Links: https://leetcode.com/problems/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:

Input: matrix = [[1,0,1],[0,-2,3]], k = 2
Output: 2 
Explanation: 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?

这道题初看如果暴力解决一定很困难，时间复杂度较高，所以不妨采用降维的思路和转化的思路。

那么本题可以先这样考虑：

先考虑一维数组下最大的连续子数组和
考虑一维数组下不超过K的最大连续子数组和（或者输出位置）
考虑二维数组的最大子矩形的和
考虑二维数组下不超过K的最大子矩形和（本题）。

一维数组下最大的连续子数组和

也就是53.Maximum Subarray，列出一个状态转移方程即可，当前元素加入前面序列，或者另起一个新的序列。 $$ \begin{aligned} d[j] &=\max {d[j-1]+S[j], S[j]}, 其中1 \leq j \leq n \ \text {target} &=\max {d[j]},其中1 \leq j \leq n \end{aligned} $$ 一维数组下不超过K的最大连续子数组和

上一个问题可以视为 $k = +\infty$ 的特殊情形，这里先不考虑输出位置。这里采用前缀和的思路，不妨设 $S_m$ 是数组前 $m$ 项的和， $S_{n-1}$ 是数组前 $n-1$ 项的和，那么 $S_m - S_{n-1}$ 就是数组从位置 $n$ 到位置 $m$ 的和，也就是一个子数组的和。原问题可以转化成：设满足 $S_m -S_n \leq k$ 的集合为可行集 $Q$ ，我们要找max_element(Q)。对于每一次查找过程，可以认为在对应次查找中， $S_m$ 和 $k$ 是固定的，也就是要去寻找 $S_n$ 的位置，因为 $S_n \geq S_m -k$ ，要使能找到 $Q$ 里面最大的值，则 $S_n$ 应该尽可能的小，也就是**第一个不小于目标值的数**，所以应选择lower_bound。时间复杂度 $O(nlog n)$ .

#include <iostream>
#include <vector>
#include <set>

using namespace std;

const int INF = 0x0ffffff;

int maxSubArray(vector<int> & nums, int k)
{
    set<int> prefixSum;
    prefixSum.emplace(0);
    int sum = 0, tmpSum = -INF;

    for (auto e : nums) {
        sum += e;
        auto pos = prefixSum.lower_bound(sum - k);
        if (pos != prefixSum.end() && sum - *pos > tmpSum) {
            tmpSum = sum - *pos;
            if (tmpSum == k){
                return tmpSum;
            }
        }
        prefixSum.emplace(sum);
    }

    return tmpSum;
}


int main()
{
    vector<int> nums = {-2,1,-3,4,-1,2,1,-5,4};
    int k = 5; //6为最大
    cout << maxSubArray(nums, k) << endl;

    return 0;
}
//输出为5

这里如果 $k$ 小于数组里的所有数，那么就输出 $-INF$ 。

题目变形，如果找小于k的最大数呢？那么相当于找upper_bound。改完后输出就是4。

相当于找 $S_m - S_n < k$ ，转化为 $S_n > S_m - k$ ，这里为了让 $S_m - S_n$ 尽可能的大，那么应该让 $S_n$ 尽可能的小，所以对应次查找可以认为目标值是 $S_m - k$ ，也就是**找第一个大于目标值的数**，也就是用函数upper_bound。

#include <iostream>
#include <vector>
#include <set>

using namespace std;

const int INF = 0x0ffffff;

int maxSubArray(vector<int> & nums, int k)
{
    set<int> prefixSum;
    prefixSum.emplace(0);
    int sum = 0, tmpSum = -INF;

    for (auto e : nums) {
        sum += e;
        auto pos = prefixSum.upper_bound(sum - k);
        if (pos != prefixSum.end() && sum - *pos > tmpSum) {
            tmpSum = sum - *pos;
            if (tmpSum == k){
                return tmpSum;
            }
        }
        prefixSum.emplace(sum);
    }

    return tmpSum;
}


int main()
{
    vector<int> nums = {-2,1,-3,4,-1,2,1,-5,4};
    int k = 5; //6为最大
    cout << maxSubArray(nums, k) << endl;

    return 0;
}
//输出为4

和不小于k的最小连续子数组和。（类似leetcode 862.Shortest Subarray with Sum at Least K）

这个问题其实和LeetCode 862只是题面类似，但是解题方法可是差别很大。题目等价于找 $S_m - S_n \geq k$ ，转化为 $S_n \leq S_m -k$ ，并且 $S_n$ 还要尽可能的大，那么目标值就是 $S_m - k$ ，相当于找最后一个不大于目标值的数，则转化为upper_bound的问题，因为upper_bound找到的是第一个大于目标值的数，那么这个数前面的就是**最后一个不大于目标值的数**。下面写出程序

#include <iostream>
#include <vector>
#include <set>

using namespace std;

const int INF = 0x0ffffff;

int maxSubArray(vector<int> & nums, int k)
{
    set<int> prefixSum;
    prefixSum.emplace(0);
    int sum = 0, tmpSum = INF;

    for (auto e : nums) {
        sum += e;
        auto pos = prefixSum.upper_bound(sum - k);
        if (pos != prefixSum.begin() && sum - *prev(pos) < tmpSum && sum - *prev(pos) >= k) {
            tmpSum = sum - *prev(pos);
            if (tmpSum == k){
                return tmpSum;
            }
        }
        prefixSum.emplace(sum);
    }

    return tmpSum;
}


int main()
{
    vector<int> nums = {-2,1,-3,4,-1,2,1,-5,4};
    int k = -7; //6为最大
    cout << maxSubArray(nums, k) << endl;

    return 0;
}

这里分别令k = -7, k = 0, k = 5, k = 10来进行验证，依次输出-5, 0, 5, INF则正确。

和大于k的最小子数组？

相当于找最后一个小于目标值的数，是lower_bound的变形问题，也就是lower_bound找到的位置，它前一个位置的数就是最后一个小于目标值的数。

#include <iostream>
#include <vector>
#include <set>

using namespace std;

const int INF = 0x0ffffff;

int maxSubArray(vector<int> & nums, int k)
{
    set<int> prefixSum;
    prefixSum.emplace(0);
    int sum = 0, tmpSum = INF;

    for (auto e : nums) {
        sum += e;
        auto pos = prefixSum.lower_bound(sum - k);
        if (pos != prefixSum.begin() && sum - *prev(pos) < tmpSum && sum - *prev(pos) > k) {
            tmpSum = sum - *prev(pos);
            if (tmpSum == k){
                return tmpSum;
            }
        }
        prefixSum.emplace(sum);
    }

    return tmpSum;
}


int main()
{
    vector<int> nums = {-2,1,-3,4,-1,2,1,-5,4};
    int k = 5; //6为最大
    cout << maxSubArray(nums, k) << endl;

    return 0;
}

验证即可。

二维数组的最大子矩形的和

一维的最大连续子数组我们已经会求了，那么二维的情况可以把他压缩成一维的情况。

//HDU 1081
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int INF = 0x0ffffff;

int maxSubArray(vector<int> & nums, int k)
{
    set<int> prefixSum;
    prefixSum.emplace(0);
    int sum = 0, tmpSum = -INF;

    for (auto e : nums) {
        sum += e;
        auto pos = prefixSum.lower_bound(sum - k);
        if (pos != prefixSum.end() && sum - *pos > tmpSum) {
            tmpSum = sum - *pos;
            if (tmpSum == k){
                return tmpSum;
            }
        }
        prefixSum.emplace(sum);
    }

    return tmpSum;
}

int maxSubArray(vector<int> & nums)
{
    int n = nums.size();
    if (n == 0) return INF;

    int res = -INF, tmpSum = 0;
    for (auto e : nums) {
        tmpSum = max(tmpSum + e, e);
        res = max(res, tmpSum);
    }

    return res;
}


int maxSubMatrix(vector<vector<int>> & nums)
{
    int m = nums.size();
    if (m == 0) return INF;
    int res = -INF;
    int n = nums[0].size();

    vector<int> subMax(n, 0);

    for (int i = 0; i < m; ++i) {
        fill(subMax.begin(), subMax.end(), 0);
        for (int j = i; j < m; ++j) {
            for (int k = 0; k < n; ++k) {
                subMax[k] += nums[j][k];
            }
            res = max(res, maxSubArray(subMax));
        }
    }

    return res;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<vector<int>> matrix(n, vector<int>(n, 0));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> matrix[i][j];
        }
    }

    cout << maxSubMatrix(matrix);

    return 0;
}

不超过k的二维数组的最大子矩形的和

如果上面的方法掌握了，那么会发现到这里只需要去把res = max(res, maxSubArray(subMax));改为res = max(res, maxSubArray(subMax, k));即可。代码见最下方。

那么扩展一下，如果要找小于k的最大子矩形和呢？改动的也只有两个地方，一个是在时间复杂度选择那里，不能出现等于的情况；另一个就是传入的maxSubArray函数的形式应该根据第二大类的讨论来进行相应修改。

进一步，如果想找不小于k的最小子矩形和呢？找大于k的最小子矩形和呢？方法就同理了。

回到本题，会发现一个很奇怪的现象，下面几段代码均可通过，但是速度却是千差万别！

先看一个超时但是思路是正确的（在倒数第二个大数据量超时）

Time Limit Exceeded.

class Solution {
int maxSubArray(vector<int> & nums, int k)
{
    set<int> prefixSum;
    prefixSum.emplace(0);
    int sum = 0, tmpSum = INT_MIN;

    for (auto e : nums) {
        sum += e;
        auto pos = prefixSum.lower_bound(sum - k);
        if (pos != prefixSum.end() && sum - *pos > tmpSum) {
            tmpSum = sum - *pos;
            if (tmpSum == k){
                return tmpSum;
            }
        }
        prefixSum.emplace(sum);
    }

    return tmpSum;
}

public:
    int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(nullptr);

        int res = INT_MIN;
        int n = matrix[0].size(), m = matrix.size();

        vector<int> subMax(n, 0);

        for (int i = 0; i < m; ++i) {
            fill(subMax.begin(), subMax.end(), 0);
            for (int j = i; j < m; ++j) {
                for (int k = 0; k < n; ++k) {
                    subMax[k] += matrix[j][k];
                }
                res = max(res, maxSubArray(subMax, k));
            }
        }

        return res;
    }
};

下面这个仅仅是改动了通过行求子数组还是列求子数组，代码就通过了。

Runtime: 380 ms
Memory Usage: 106.5 MB

class Solution {
int maxSubArray(vector<int> & nums, int k)
{
    set<int> prefixSum;
    prefixSum.emplace(0);
    int sum = 0, tmpSum = INT_MIN;

    for (auto e : nums) {
        sum += e;
        auto pos = prefixSum.lower_bound(sum - k);
        if (pos != prefixSum.end() && sum - *pos > tmpSum) {
            tmpSum = sum - *pos;
            if (tmpSum == k){
                return tmpSum;
            }
        }
        prefixSum.emplace(sum);
    }

    return tmpSum;
}

public:
    int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(nullptr);

        int res = INT_MIN;
        int n = matrix[0].size(), m = matrix.size();

        if (m * m * n < n * n * m) {
            for (int i = 0; i < m; ++i) {
                vector<int> subMax(n, 0);
                for (int j = i; j < m; ++j) {
                    for (int k = 0; k < n; ++k) {
                        subMax[k] += matrix[j][k];
                    }
                    res = max(res, maxSubArray(subMax, k));
                }
            }
        }
        else{
            for (int i = 0; i < n; ++i) {
                vector<int> subMax(m, 0);
                for (int j = i; j < n; ++j) {
                    for (int k = 0; k < m; ++k) {
                        subMax[k] += matrix[k][j];
                    }
                    res = max(res, maxSubArray(subMax, k));
                }
            }
        }

        return res;
    }
};

这个版本增加了一步判断，如果连续子数组的最大值都小于k，那么就没必要去寻找不超过k的子数组了，相当于节省了比较费时的一步。这里其实应该可以直到，毕竟找最大连续子数组时间复杂度是 $O(n)$ ，而找不超过k的连续子数组时间复杂度是 $O(nlog n)$ 。很明显，时间降了一半。

Runtime: 128 ms
Memory Usage: 11.1 MB

class Solution {
int maxSubArray(vector<int> & nums, int k)
{
    set<int> prefixSum;
    prefixSum.emplace(0);
    int sum = 0, tmpSum = INT_MIN;

    for (auto e : nums) {
        sum += e;
        auto pos = prefixSum.lower_bound(sum - k);
        if (pos != prefixSum.end() && sum - *pos > tmpSum) {
            tmpSum = sum - *pos;
            if (tmpSum == k){
                return tmpSum;
            }
        }
        prefixSum.emplace(sum);
    }

    return tmpSum;
}

int maxSubArray(vector<int> & nums)
{
    int n = nums.size();
    if (n == 0) return INT_MIN;

    int res = INT_MIN, tmpSum = 0;
    for (auto e : nums) {
        tmpSum = max(tmpSum + e, e);
        res = max(res, tmpSum);
    }

    return res;
}

public:
    int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
        int res = INT_MIN;
        int n = matrix[0].size(), m = matrix.size();

        for (int i = 0; i < m; ++i) {
            vector<int> subMax(n, 0);
            for (int j = i; j < m; ++j) {
                for (int k = 0; k < n; ++k) {
                    subMax[k] += matrix[j][k];
                }
                int tmp = maxSubArray(subMax);
                if (tmp <= k) {
                    res = max(res, tmp);
                    continue;
                }
                res = max(res, maxSubArray(subMax, k));
            }
        }


        return res;
    }
};
auto gucciGang = []() {std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

来看看讨论区的20ms的解法和我的差别在哪里。差别在于它只选择通过列来寻找。速度是20ms。

class Solution {
public:
    int maxSumSubmatrix(vector<vector<int>>& matrix, int maxS) {
        int maxA = INT32_MIN, r = matrix.size(), c = matrix[0].size();
        for(int i = 0; i < c; ++i) {
            vector<int> sum(r, 0);
            if(maxA == maxS) return maxA; // Stop if we can reach maxS
            for(int j = i; j < c; ++j) {
                for(int k = 0; k < r; ++k) sum[k] += matrix[k][j];

                //First try Kadane's Algo and see if maxSum is less than maxS. 
                int curMax = INT32_MIN, curSum = 0;
                for(int k = 0; k < r; ++k) {
                    curSum += sum[k];
                    curMax = max(curMax, curSum);
                    if(curSum < 0) curSum = 0;
                }
                if(curMax <= maxS) {maxA = max(maxA, curMax); continue;}

                // Only apply slow method when there maxSum that is greater than maxS.
                int csum = 0;
                set<int> s({csum});
                for(int k = 0; k < r; ++k) {
                    csum += sum[k];
                    auto it = s.lower_bound(csum - maxS);
                    if(it != s.end()) maxA = max(maxA, csum - *it);
                    s.insert(csum);
                }
            }
        }
        return maxA;
    }
};

auto gucciGang = []() {std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

于是我把刚刚运行128ms的代码改成通过按列来寻找，速度确实立刻到了16ms。

Runtime: 16 ms
Memory Usage: 11 MB

class Solution {
int maxSubArray(vector<int> & nums, int k)
{
    set<int> prefixSum;
    prefixSum.emplace(0);
    int sum = 0, tmpSum = INT_MIN;

    for (auto e : nums) {
        sum += e;
        auto pos = prefixSum.lower_bound(sum - k);
        if (pos != prefixSum.end() && sum - *pos > tmpSum) {
            tmpSum = sum - *pos;
            if (tmpSum == k){
                return tmpSum;
            }
        }
        prefixSum.emplace(sum);
    }

    return tmpSum;
}

int maxSubArray(vector<int> & nums)
{
    int n = nums.size();
    if (n == 0) return INT_MIN;

    int res = INT_MIN, tmpSum = 0;
    for (auto e : nums) {
        tmpSum = max(tmpSum + e, e);
        res = max(res, tmpSum);
    }

    return res;
}

public:
    int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
        int res = INT_MIN;
        int n = matrix[0].size(), m = matrix.size();

        for (int i = 0; i < n; ++i) {
            vector<int> subMax(m, 0);
            for (int j = i; j < n; ++j) {
                for (int k = 0; k < m; ++k) {
                    subMax[k] += matrix[k][j];
                }
                int tmp = maxSubArray(subMax);
                if (tmp <= k) {
                    res = max(res, tmp);
                    continue;
                }
                res = max(res, maxSubArray(subMax, k));
            }
        }


        return res;
    }
};
auto gucciGang = []() {std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

通过上面的一系列探索，可以发现有两个关键点：

在时间复杂度是 $O(n)$ 和 $O(nlog n)$ 的判断选择上，这个必须有才能进行加速。
在通过行还是列来进行搜索区别很大，也就是总体时间复杂度或者是 $O(m^2nlogn)$ ，或者是 $O(n^2mlogm)$ ，所以比较m*m*n和n*n*m很有必要。

此题只是恰好通过列来搜索较优，实际上需要在最开始就进行一次判断，可自行测试。