AcWing 126. 最大子矩阵的和

  • 这道题目的数据范围是100

    朴素做法最大子矩阵的和 - 图2

  • 最大子矩阵的和 - 图3级别的运算数量，有可能会超时 ```cpp

    include

    using namespace std;

define N 110

int n; int g[N][N]; int s[N][N];

int main() { // input data cin >> n; for (int i = 1; i <= n; i ++) { for (int j = 1; j <= n; j ++) { cin >> g[i][j]; // get prefix sum of g s[i][j] = g[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1]; } }

  1. int ans = -1e9;
  2. for (int i = 1; i <= n; i ++) {
  3.     for (int j = 1; j <= n; j ++) {
  4.         for (int a = i; a <= n; a ++) {
  5.             for (int b = j; b <= n; b ++) {
  6.                 // get every area of left top point (i, j) from right bottom point (a, b)
  7.                 int area = s[a][b] - s[i - 1][b] - s[a][j - 1] + s[i - 1][j - 1];
  8.                 ans = max(area, ans);
  9.             }
  10.         }
  11.     }
  12. }
  13. cout << ans << endl;
  14. return 0;

}

  1. <a name="N7Q2N"></a>
  2. ### 降维优化![](https://cdn.nlark.com/yuque/__latex/4a7d22b39e93fbbcbe107e7a19e8bd34.svg#card=math&code=O%28n%5E3%29&height=23&width=43)
  4. - 先考虑一维的问题：在一维数组中找到以每个数结尾的最大连续序列之和
  5. - 比如说：{1, -2, 4, -5, 6, 7, 10}
  6. - 这个问题其实可以通过dp来求解，每个数结尾的最大连续序列之和 只和 前一个数的最大连续序列之和有关系
  7. - 因此有如下转换方程：f[i] = max(0, f[i - 1]) + w[i]
  8. - 因此一维问题可以通过O(n)的时间复杂度来求解
  10. - 受一维问题的启发，我们可以通过固定上下边界，把问题转化为一个一维问题，因此可以通过![](https://cdn.nlark.com/yuque/__latex/4a7d22b39e93fbbcbe107e7a19e8bd34.svg#card=math&code=O%28n%5E3%29&height=23&width=43)的复杂度求解该问题
  11. ```cpp
  12. #include <iostream>
  13. using namespace std;
  15. #define N 110
  16. int g[N][N];
  17. int s[N][N];
  18. int n;
  20. int main()
  21. {
  22.     cin >> n;
  23.     for (int i = 1; i <= n; i ++) {
  24.         for (int j = 1; j <= n; j ++) {
  25.             cin >> g[i][j];
  26.             s[i][j] = g[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
  27.         }
  28.     }
  30.     int ans = -1e9;
  31.     for (int i = 1; i <= n; i ++) {
  32.         for (int a = i; a <= n; a ++) {
  33.             int last = -1e9;
  34.             for (int k = 1; k <= n; k ++) {
  35.                 // area of from (i, k) to (a, k)
  36.                 int cur = s[a][k] - s[a][k - 1] - s[i - 1][k] + s[i - 1][k - 1];
  37.                 last = max(0, last) + cur;
  38.                 ans = max(ans, last);
  39.             }
  40.         }
  41.     }
  42.     cout << ans << endl;
  43.     return 0;
  44. }
  • 另外这里存放的数据和代码量其实可以进一步优化。
  • 我们其实需要的是快速求某两列之间的和，因此我们对s[i][j]的数组定义，第j列，第0行到底i行的前缀和 ```cpp

    include

    using namespace std;

define N 110

int g[N][N]; int s[N][N]; int n;

int main() { cin >> n; for (int i = 1; i <= n; i ++) { for (int j = 1; j <= n; j ++) { cin >> g[i][j]; s[i][j] = g[i][j] + s[i - 1][j]; } }

  1. int ans = -1e9;
  2. for (int i = 1; i <= n; i ++) {
  3.     for (int a = i; a <= n; a ++) {
  4.         int last = 0;
  5.         for (int k = 1; k <= n; k ++) {
  6.             last = max(0, last) + s[a][k] - s[i - 1][k];
  7.             ans = max(ans, last);
  8.         }
  9.     }
  10. }
  11. cout << ans << endl;
  12. return 0;

}

  1. <a name="ifgOR"></a>
  2. ## [LeetCode 363. Max Sum of Rectangle No Larger Than K](https://leetcode-cn.com/problems/max-sum-of-rectangle-no-larger-than-k/)
  4. - 首先肯定的是用![](https://cdn.nlark.com/yuque/__latex/813eac21bcd081b4091d26c0acc401bb.svg#card=math&code=O%28n%5E4%29&height=23&width=43)的时间复杂度正确性是没什么问题，但时间超限了
  5. - 虽然上面的动态规划思路不适用于该题，但我们可以借用上面的思路尝试思考下
  6. - 我们固定左右两条边(y1, y2)，并且固定下边这条边(x2)，我们看第四个维度（上边）是否可以优化
  7. - 我们通过前缀和的想法来进一步思考，我们有一个前缀和s2(1，y1, x2, y2)，根据题意，我们要求符合s2 - si <= k，s2 - si的最大值，变换了之后si >= s2 - k，由于s2和k固定，因此我们需要求一个前缀和si 符合 >= s2 - k的最小值，及c++中std:set的lower_bound函数的含义 
  8. - 因此，我们固定左右边界，可以枚举每一个下边，然后根据之前存在set中的数据，求一个符合的si，更新结果，直到矩阵底部，最终的复杂度为![](https://cdn.nlark.com/yuque/__latex/98bc60afa7f01b2a5901466508aa4d04.svg#card=math&code=O%28n%5E3log%5C%20n%29&height=23&width=78)
  9. ```cpp
  10. class Solution {
  11. public:
  12.     int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
  13.         int n = matrix.size();
  14.         int m = matrix[0].size();
  15.         vector<vector<int>> presum(n + 1, vector<int>(m + 1, 0));
  16.         for (int i = 1; i <= n; i ++) {
  17.             for (int j = 1; j <= m; j ++) {
  18.                 presum[i][j] = matrix[i - 1][j - 1] + presum[i - 1][j] + presum[i][j - 1] - presum[i - 1][j - 1];
  19.             }
  20.         }
  22.         int ans = -1e9;
  23.         // left bound
  24.         for (int y1 = 1; y1 <= m; y1 ++) {
  25.             // right bound
  26.             for (int y2 = y1; y2 <= m; y2 ++) {
  27.                 // S(i) represent sum area of (1, y1) to (i, y2)
  28.                 // presum
  29.                 set<int> S;
  30.                 // insert S_0
  31.                 S.insert(0);
  32.                 // bottom bound
  33.                 for (int x2 = 1; x2 <= n; x2 ++) {
  34.                     int S_x2 = presum[x2][y2] + presum[0][y1 - 1] - presum[x2][y1 - 1] - presum[0][y2];
  35.                     // we need max value of (S_x2 - S_x1) when S_x2 - S_x1 <= k
  36.                     // x2 is no changed, so we need min value of S_x1 when S_x1 >= S_x2 - k;
  37.                     auto it = S.lower_bound(S_x2 - k);
  38.                     if (it != S.end()) {
  39.                         ans = max(ans, S_x2 - *it);
  40.                     }
  41.                     S.insert(S_x2);
  42.                 }
  43.             }
  44.         }
  45.         return ans;
  46.     }
  47. };