动态规划法求最大子矩阵和

问题描述

给定某二维矩阵,求出其所有子矩阵中所有元素之和最大者。

样例

INPUT

0 -2 -7  0
9  2 -6  2
-4  1 -4  1
-1  8  0 -2 

OUTPUT

15

解法及代码

其实求最大子矩阵和的关键思想,就是将问题转化为最大子数组问题。

假定我们已经知道某个子矩阵是最大子矩阵,那么将这个二维的矩阵从上到下”拍扁”(同一列中各行元素相加),就变成了一个一维的数组,那么也就转化成了求最大子数组的问题。

所以,我们只需要将所有可能的一维数组构造出来,分别求出最大子数组,然后取其中最大者即可得到最大子矩阵和。

代码如下:

吃桔子的攻城狮

修炼ing……

在 “动态规划法求最大子矩阵和” 上有 2 条评论

发表评论