最大子矩阵

前缀和 + 最大子序和

提示

此处的序指的是连续的子数组， 而不是序列

class Solution {
 public:
  vector<int> getMaxMatrix(vector<vector<int>>& matrix) {
    int n = matrix.size(), m = matrix[0].size(), maxVal = INT32_MIN;
    vector<int> ans;
    vector<vector<int>> dp(n + 1, vector<int>(m + 1));
    for (int i = 1; i <= n; ++i) {
      for (int j = 1; j <= m; ++j) {
        dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] +
                   matrix[i - 1][j - 1];
      }
    }

    for (int up = 1; up <= n; ++up) {
      for (int down = up; down <= n; ++down) {
        int val = 0, left = 1;
        for (int right = 1; right <= m; ++right) {
          val = dp[down][right] - dp[down][left - 1] - dp[up - 1][right] +
                dp[up - 1][left - 1];
          if (val > maxVal) {
            maxVal = val;
            ans = {up - 1, left - 1, down - 1, right - 1};
          } else if (val < 0) {
            left = right + 1;
          }
        }
      }
    }
    return ans;
  }
};