1224 最大子矩阵(动态规划+最大子段和)

最大子矩阵:
1.朴素解法(6 层循环)
两层循环枚举所有的左上角点(lx，ly)
两层循环枚举所有的右下角点(rx，ry)
两层循环针对左上角点(lx,ly)到右下角点(rx，ry)围成的矩阵求和
2.一维前缀和优化(5 层循环)
两层循环枚举所有的左上角点(lx，ly)
两层循环枚举所有的右下角点(rx，ry)
一次循环枚举 lx 到 rx行，针对每一行利用一维前缀和求解[ly,ry]的
区间和
3.二维前缀和优化(4 层循环)
两层循环枚举所有的左上角点(1x，1y)
两层循环枚举所有的右下角点(rx，ry)
使用二维前缀和直接求解左上角点(1x,1y)到右下角点(rx，ry)围成的
矩阵求和
4.维度压缩+最大子段和 dp 思想优化(3 层循环)
两层循环枚举所有的 i1 行和 i2 行
一层循环求解 i1 行到 i2 行之间的最大子矩阵，具体步骤如下:
1.先将 i1 行到 i2 行每一列进行求和(这里使用一维前缀和进行处理)
这样每一列就压缩成一个点，那么 1~n 列就构成了n个点
2.然后对这个 n个点求解最大子段和即 i1~i2 的最大子矩阵

我们首先将所有列的每一行的前缀和求出来，便于后续压缩

之后我们对于所有i1行 到 i2行范围之间的所有列的最大子段和进行求解，在这个过程中，我们将i1行到i2行之间的所有列的前缀和求解作为dp[j]进行存储，这样二维问题就变成了一个点，问题就变成了求解一维数组的最大子段和问题

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

const int N = 1e3 + 10;
#define int long long 

int a[N][N], dp[N];
int presum[N][N];


signed main() {

	int n; cin >> n;
	
	for (int i = 1; i <= n;i++) {
		for (int j = 1; j <= n;j++) {
			cin >> a[i][j];
			presum[i][j] = presum[i - 1][j] + a[i][j];//代表第j列前i行的元素和
		}
	}
	int mx = -127 * n * n;

	//确定上下两行，求两行之间所有列的“最大子段和”
	for (int i1 = 1; i1 <= n;i1++) {
		for (int i2 = i1; i2 <= n;i2++) {
			for (int j = 1; j <= n;j++) {
				//二维问题转化为一维数组的最大子段和
				dp[j] = presum[i2][j] - presum[i1 - 1][j];
			}
			for (int j = 1; j <= n;j++) {
				dp[j] = max(dp[j],dp[j-1]+dp[j]);
				mx = max(mx, dp[j]);
			}
		}
	}
	cout << mx<<endl;

	return 0;
}