矩阵累加运算中累加号的意思

来源：蜘蛛抓取(WebSpider) 时间：2019-04-17 02:42 标签： 矩阵累加

版权声明：本文为博主原创文章未经博主允许不得转载。 /qq_/article/details/

　　给定一个矩阵累加matrix其中的值有正、有负、有0，返回子矩阵累加的最大累加和
　　例如，matrix为：
　　其中朂大累加和的子矩阵累加为：

　　首先看这样一个例子假设一个2行4列的矩阵累加如下：
　　如何求必须含有2行元素的子矩阵累加中的最夶累加和？可以把两列的元素相加然后得到累加数组[-1, 7, -6, 4]，接下来求这个累加数组的最大累加和结果就是7，且这个子矩阵累加数：
　　也僦是说如果一个矩阵累加一共有k行且限定必须含有k行元素的情况下，我们只要把矩阵累加的每一列的k个元素累加生成一个累加数组然後求出这个数组的最大累加和，这个最大累加和就是必须含有k行元素的子矩阵累加中的最大累加和
　　对于整个N*N的矩阵累加来说，我们需要考虑以第一行开头的一行矩阵累加、两行矩阵累加、三行矩阵累加…N行矩阵累加；以及以第二行开头的一行矩阵累加、二行矩阵累加…N-1行矩阵累加；……以最后一行开头的一行矩阵累加将所有的这些情况中的最大累加和找到即可。一共有O(N2)中情况找到的时间复杂度是O(N)，所以最终的时间复杂度是O(N3)

我要回帖

更多关于 矩阵累加 的文章

 

随机推荐