【POJ 1050】To the Max（降维，贪心，最大子区间和）

题面：To the Max

题目大意

给定一个整数 $n$ ，代表的是方形区间的边长，之后再输入所有格子内的数。 求该区间内的最大子区间的和。

思路

暴力要搞到 $O(n^4)$。考虑一下降维和动归。 正常动归，要用到二维动态规划，可能会超时。

这里可以将每一列的前缀和算出来，即把每一列当作一个数，在确定好上下界之后，就可以用一维动归来解决这个问题了。 算法的时间复杂度就降到了 $O(n^3)$

贪心思想

在做一维动归的时候，需要一些贪心思想。 遍历到第 $k$ 个数时，如果前面 $[1,k-1]$ 个数的总和 $last\_sum\le 0$，那么说明我们可以将这第 $k$ 个数当作一个新的区间的开始。假设还加进 $last\_sum$ 的话，此时 $last\_sum+a[k]\le a[k]$，则这个情况一定不是最优的，所以可以摒弃 $last\_sum$。

代码

#include <bits/stdc++.h> #define sc scanf #define pf printf using namespace std; const int N = 110; int n; int g[N][N]; int main() { sc("%d", &n); for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) { sc("%d", &g[i][j]); //这里计算每一列的前缀和 g[i][j] += g[i - 1][j]; } int ans = INT_MIN; //用i确定上界 for(int i = 1; i <= n; i++) //用j确定下界 for(int j = i; j <= n; j++) { int last = 0;//记录已经遍历过的总和。 for(int k = 1; k <= n; k++) { //如果last<=0，则让其等于0. //g[j][k] - g[i-1][k] 计算的是上界 i 到下界 j的区间和 //子区间为 [i + x, i + k, j + x, j + k] //其中 x 为last的起点，也可能为 k。 last = max(last, 0) + g[j][k] - g[i - 1][k]; ans = max(ans, last); } } pf("%d\n", ans); return 0; }