[蓝桥杯][历届试题]最大子阵

题目

题目链接

题解

动态规划。压缩+最大子段和，属于最大子段和变形题。

最大子段和应该比较清楚。 转移方程：dp[i] = max(dp[i-1] + a[i], a[i])，其中dp[i]表示以第i个元素结尾的子段和的最大值。 当dp[i-1]=0时，说明加上前面子段和最大值会对以a[i]结尾的最大子段和做出正贡献，那么加上。

接下来我们将一维的最大子段和问题扩展到二维。

先看2行m列的情况： 对于第一行而言，我们可以通过上面讲到的“最大子段和”思想求出1×m的矩阵（或向量）中的最大子矩阵； 同样的，对于第二行而言，我们也可以求出1×m的矩阵中的最大子矩阵；

这样就包含了全部矩阵中的哪些情况呢？ 这相当于在一个元素个数为2×m的矩阵中已经判断完全部格式为1×t的子矩阵中的最大子矩阵，其中1 n>>m; for(int i = 1;i a[i][j]; for(int i = 1;i