我在洛谷写的这题的题解中有一处小小的笔误，不影响阅读，就不更正了，但在 Hydro 上已经更正。

• 原题面
• 更好的阅读体验

题目大意 ：给出一个 $m \times n$ 的矩阵，求出这个矩阵的最大子矩阵和。（把题目中的 $0$ 在读入时当做 $-1$ 处理即可，下文不再赘述）

具体思路 ：

1. 求出每一行前 $j$ 个数的前缀和。即：

   $$sum_{i,j} = sum_{i,j-1} + a_{i,j}$$

   其中，$sum_{i,j}$ 表示第 $i$ 行前 $j$ 个数的前缀和。

2. 进行枚举起始列 $i$ 与目标列 $j$，再把每一行中从 $i$ 到 $j$ 的和算出来（利用之前的前缀和），我们可以建立一个 临时 数组f，则：

   $$f_k = sum_{k,j} - sum_{k,i-1}$$

   其中，$f_k$ 表示第 $k$ 行中从 $i$ 到 $j$ 的和。

3. 这时，我们已经把每一行（从 $i$ 到 $j$）的和存到了数组 $f$ 中，那么我们就可以把问题转化为 最大子段和 问题了。最大子段和的公式：

   $$f_k = \max(f_k, f_k + f_{k - 1})$$

   再用变量 $ans$ 打擂台求出 $f_k$ 的最大值即可。

AC Code ：

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define maxn 405
int m, n, ans;
int sum[maxn][maxn], f[maxn];
char c;

signed main() {
    cin >> m >> n;
    //注意不是 n 行 m 列

    for (int i = 1; i <= m; i++) 
        for (int j = 1; j <= n; j++) {
            cin >> c;
            if (c == '1') sum[i][j] = sum[i][j - 1] + 1;
            else if (c == '0') sum[i][j] = sum[i][j - 1] - 1;
        }
    //求出每一行的前 j 个数的前缀和

    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j++) {//枚举第 i 列到第 j 列
            
            for (int k = 1; k <= m; k++) 
                f[k] = sum[k][j] - sum[k][i - 1];//把每一行的和算出来

            for (int k = 1; k <= m; k++) {
                f[k] = max(f[k], f[k] + f[k - 1]);
                ans = max(ans, f[k]);
            }//最大子段和问题

        }
    cout << ans << endl;
    return 0;
}