思路
最朴素的想法是枚举左上角和右下角,要用 $4$ 个 for
循环,加上二维前缀和,复杂度 $O(n^4)$。
我们进行优化:
枚举边界,如下图所示:边界 $1$、边界 $2$ 和边界 $3$ 就是枚举的边界。
把边界 $1$ 和边界 $2$ 之间的每一列看做一个整体(图中的相同颜色),每个整体的值就是这些元素的累加和,我们枚举边界 $3$,找出一边界 $3$ 作为右边界的最优矩形。
找矩形的方法:
假设有数组 $a$,我们用 $f_i$ 表示已 $i$ 为终点的最大连续和。
- 如果 $f_{i - 1} > 0$,$f_i = a_i + f_{i - 1}$;
- 如果 $f_{i - 1} \leq 0$,$f_i = a_i$。
我们可以用前缀和求出整体的累加和,然后再用上面求 $f$ 数组的方法求出最优矩形。
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
using namespace std;
const int N = 110;
long long a[N][N];
int main()
{
long long n, ans = -0x3f3f3f3f;
cin >> n;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
cin >> a[i][j];
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
a[i][j] += a[i - 1][j];
for (int i = 1; i <= n; i ++ )
for (int j = i; j <= n; j ++ )
{
long long sum = 0;
for (int k = 1; k <= n; k ++ )
{
sum = max(sum, 0ll) + a[j][k] - a[i - 1][k];
ans = max(ans, sum);
}
}
cout << ans << endl;
return 0;
}
%%%思路很巧妙!