一、主题说明：现给出N*N矩阵，要求求具有最大和的部分矩阵之和。 示例如下图所示。
其最大的子矩阵之和为15
二、解题思路该问题的解法与动态规划经典问题——最大连续子序列的和问题思想相同，但正题是二维空间上的拓展。 N*N矩阵由二维阵列a[N][N]表示。 我们解决新问题的方法借鉴了我们以前解决的类似问题的方法和思路，当然正题也不例外，通过思考可以看出，这个问题与经典问题——最连续子串之和非常相似。 只是，动态规划经典问题——最大连续子串之和是一维问题，但正题是二维问题，我们能把二维问题变成一维问题吗？ 认真想想就好了。 可以将各列的元素组合成一个元素。 (可以定义二维数组sum[][]。 其中，sum[i]表示前I行中每列数字相加的和。 因此，sum[j][] - sum[i][]是一维向量。 以这种方式动态规划经典主题——的最大连续子串之和
定义状态根据上述分析，二维数组dp[i][j]定义为表示从第I行至第j行的最大部分矩阵和。 因此，我们要求的最大部分矩阵和是max(DP[I][j] )中的0Ijn；
定义状态转移方程，知道动态规划满足无后向性。 也就是说，各阶段的决策只受到以前决策的影响，但不影响之后各阶段的决策。 因此，我们可以从后向前推出状态转移方程，具体定义可以参考动态规划经典问题——最连续子序列之和的状态转移方程。
三、代码编写# include stdio.h # include stdlib.h # definen4# definemax (a，b ) ) a b )？ a:b ) int main () /定义矩阵inta[n] () (0，-2，- 7，0 )、{ 9，2，- 6，2 }、{-4，1，- 4，1 }、{-1} //2 其中，sum[i]表示前I行中每列数字相加的和。 //，所以sum[j][] - sum[i][]是一维向量int sum[N 1][N]={0}； int temp=0； //在保存最大子矩阵和int maxResult=0的//sum数组中输入int i、j、k； for(I=1； i N 1； I ) for(j=0； j N； j ) { sum [ I ] [ j ]=sum [ I-1 ] [ j ] a [ I-1 ] [ j ]； //核心算法for(I=0； i N； I ) for(j=I1； j N 1； j () { temp=0； for(k=0； k N； k ) ) temp=(sum[j][k]-sum[I][k]； if(tempmaxresult ) { maxResult=temp； (if ) { temp=0) { temp=0； } } } } printf ('最大子矩阵和为%d '，maxResult )； 返回0； (四、运行结果