描述
题解
这个问题其实和普通的求最大子矩阵相仿,不过在判断是否可以构成矩阵时需要进行特别的判断,A[j][k] - A[i - 1][k] != j - i + 1
,为真,则需要进行重置,否则,进行cnt++
。
但是这个问题还有更加高级的解法,可以用单调栈做,不过个人感觉有些复杂,这里只提供最简单的解法,也就是最大子矩阵解法。如果矩阵再大一些,那就只能用单调栈搞事情啦。也许还有别的方法,那我就不清楚了。
代码
#include <iostream>
using namespace std;
const int MAXN = 505;
int A[MAXN][MAXN];
int main(int argc, const char * argv[])
{
int m, n;
cin >> m >> n;
for (int i = 1; i <= m; i++)
{
for (int j = 1; j <= n; j++)
{
scanf("%d", A[i] + j);
A[i][j] += A[i - 1][j];
}
}
int ans = 0;
for (int i = 1; i <= m; i++)
{
for (int j = 1; j <= m; j++)
{
int cnt = 0;
for (int k = 1; k <= n; k++)
{
if (A[j][k] - A[i - 1][k] != j - i + 1)
{
ans = max(ans, cnt * (j - i + 1));
cnt = 0;
}
else
{
cnt++;
}
}
ans = max(ans, cnt * (j - i + 1));
}
}
cout << ans << '\n';
return 0;
}