上几篇博客我们讲到了最大子段和，我们根据动态规划的思想，是可以得到其的递推公式。
下面我们先分析关于一维的最大字段和的求解过程：
如果给定一个数组 a[n],求其最大的子段。那么，我们会很容易的想到，运用暴力求解的方式，通过二维的遍历。但是其时间复杂度是O（n*n),显然当数据规模很大时，其肯定时tle的。
所以应该利用动态规划的思想进行优化，那么优化如何着手呢。我们仍然回归到暴力求解方法中去，暴力方法就是将子段的所有的情况都列举出来，并且一一相加求和，最后得出了最大值。例如此数组有四个元素，那么子段的情况可能是(a[0],a[1])、(a[0],a[2])、（a[0],a[1],a[2]),等等。我们可以发现，计算机其实执行了许多的重复操作。但我们列举的数组长度是从小到大时，其实到了最后我们计算长数组值时，有计算了一遍小数组的值，如上面的例子。所以这就是我们优化的方向，它也满足了动态规划的基本特征，就是其有多个重复的子问题。那么我们可以以空间换时间，申请空间，记录计算机运算过的值。
延续思路，我们可以申请dp数组，同时我们可以得到递推公式：dp[i]=max(dp[i-1]+a[i],a[i]),最后我们再从dp数组中，挑出最大的。就完成了问题的求解。
ok，我们大致分析了一维的最大子段和，那么我们来解决关于二维矩阵的最大子矩阵和。
解决二维问题，我们可以将其降维，我们能否找到一种措施，使其降维成一维的类似问题？
例题如下：
求一个M*N的矩阵的最大子矩阵和。 比如在如下这个矩阵中： 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 拥有最大和的子矩阵为： 9 2 -4 1 -1 8 其和为15。
我们可以发现，关于一维的最大子段和问题解决得基础是dp数组得不断延伸，就是dp数组通过前一状态不断得到现在状态的最有情况。这也是二维问题解决的基础。我们可以通过列的前缀和进行列的压缩，使得一竖列累加变为一个值，这样一个小矩阵就变成了一个数组。这也就完成了，降维的操作。最后根据一维的代码可以完成后续的操作。
#include<iostream> using namespace std; int main(){ int n,m; cin >> n >> m; long long a[n+1][m+1]; long long pre[n][m]; long long ans=-1e9; long long sum; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin >> a[i][j]; } } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ ans=max(ans,a[i][j]); } } if(ans<0){ cout << ans; } else{ for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++) pre[i][j]=pre[i-1][j]+a[i][j];//压缩整个j列 } for(int i=1;i<=n;i++){//不断的变换上下界， for(int j=i;j<=n;j++){ sum=0; for(int k=1;k<=m;k++){//这里并没有到dp数组，因为我们用了ans，其是动态的，一直保持现在的最大值。然而dp数组，最后需要遍历找出其最大值。思想上大同小异。 if(sum+pre[j][k]-pre[i][k]<0) sum=0; else{ sum+=pre[j][k]-pre[i][k]; ans=max(ans,sum); } } } } cout << ans ; } return 0; }
