矩阵前缀和应用1：最大和子矩阵 前缀和+动态规划

关于矩阵前缀和【矩阵前缀和：常数时间求一子矩阵的加和】

给一个m*n的矩阵，找到一个子矩阵使其里面的数字加和最大，输出这个最大值

首先想到暴力算法：
枚举矩阵行列，复杂度O(n⁴)，然后对每个枚举的子矩阵，计算矩阵内的加和O(n²)，总复杂度O(n⁶)

通过前缀和，可以把计算加和的时间变为O(1)，总复杂度O(n⁴)，还是有点大

优化：引入动态规划中的最大子区间问题

【类似的题目】

已知一个一维数组，如何求一区间使得区间内加和最大？暴力枚举左右端点的复杂度O(n²)，但是动态规划可以O(n)完成

定义状态
dp[i]表示以下标 i 的元素结尾的某个子区间的最大加和

状态转移
对于以下标 i 元素结尾的子区间，必须选取下标i的元素，但是可以主动选择是否丢弃前面的区间

1. 下标i元素 a[i]加在【以 i-1 下标结尾的最大和子区间】后面
2. 下标 i 元素单独形成一个子区间

比较两个结果，选取大的作为当前 i 下标结尾的区间的答案

最后遍历区间右端点，找最大即可

回到矩阵的问题：

现在我们已知用O(n)时间求一个一维数组最大子区间的问题，那么对于矩阵，我们可以花费O(n²)的时间，枚举起始行和结束行

在起始行和结束行已经确定的情况下，只要确定起始列，和结束列，就能够确定一个矩阵，那么我们套用上面的动态规划，对所有的列，确定一个区间使得在这个区间内，被起始行和结束行夹逼的列区间，加和值最大（加和值通过前缀和可以O(1)查询）

确定起始列，结束列，相当于一维数组的区间左端点，右端点

这里枚举起始行，结束行，起到降维的效果

O(n²)枚举起始行，结束行，再用O(n)时间找到最大的区间，总复杂度O(n³)

代码

#include <bits/stdc++.h>

using namespace std;

int a[1509][1509], dp[1509];
int m, n, x1, y1, x2, y2;

int kksum(int x1, int y1, int x2, int y2)
{
	return a[x2][y2]-a[x1-1][y2]-a[x2][y1-1]+a[x1-1][y1-1];
}

int main()
{	
	cin>>m>>n;
	memset(a, 0, sizeof(a));
	// 计算行前缀和 
	for(int i=1; i<=m; i++)
		for(int j=1; j<=n; j++) 
			cin>>a[i][j], a[i][j]+=a[i][j-1]; 
	// 计算列前缀和 
	for(int i=1; i<=m; i++)
		for(int j=1; j<=n; j++)
			a[i][j] += a[i-1][j];
	
	int ans=INT_MIN; dp[0]=INT_MIN;
	for(int r1=1; r1<=m; r1++)
	{
		for(int r2=r1; r2<=m; r2++)
		{
			// dp求起始行r1，结束行r2之间的最大子区间 
			dp[1] = kksum(r1, 1, r2, 1);
			for(int i=2; i<=n; i++)
				dp[i] = max(dp[i-1]+kksum(r1, i, r2, i), kksum(r1, i, r2, i));
			// 枚举结束列，找最大值，尝试跟新答案 
			int maxval = dp[max_element(dp, dp+n+1)-dp];
			ans = max(ans, maxval);
		}
	}
	
	cout<<ans<<endl;
	
	return 0;
}

/*
5 6
-1 -8 9 -123 123 3
77 9 18 -5 -33 9
-99 -77 321 -9 0 7
0 12 -11 0 85 54
0 1 -1 0 -1 0

4 4
0 0 0 0
0 1 1 0
0 1 1 0
0 0 0 0

3 4
-1 -2 3 -4
-5 6 -7 8
9 10 -11 -12
*/