给定一个由整数元素构成的矩阵，问题是找到最大和子矩阵。可以使用Kadane算法来解决2D矩阵的问题，该问题在这里被规定和解决here。
现在我想要解决更高维度的问题，即在d维空间中给定一个矩阵，设计一个算法来解决相同的问题。
我想知道您是否能够在
任何想法都会受到赞赏。
现在我想要解决更高维度的问题，即在d维空间中给定一个矩阵，设计一个算法来解决相同的问题。
我想知道您是否能够在
O(n^(2d-1))的时间内完成。任何想法都会受到赞赏。
1个回答
0
您可以使用多维累加表计算d维子矩阵的总和，需要进行2^d次查找、2^d/2次减法和(2^d/2)-1次加法。
累加表是一个与输入矩阵具有相同维度和大小的矩阵，其中每个元素都是输入矩阵中所有索引小于或等于该元素的所有元素的总和。它可以通过对矩阵进行单次遍历来计算。
然后，您可以通过在开始索引和子矩阵大小的每个维度上迭代，并使用总面积表计算这些开始索引和大小的子矩阵的子矩阵和，在O(n^2d)中找到最大和子矩阵。基本上，您在SAT中查找子矩阵的所有“角落”，并添加或减去该值以获取子矩阵和。当d为奇数时，对于每个角落，如果该角落具有奇数个维度，其中它是子矩阵范围的结束索引，则将其添加，如果它具有偶数个维度，则将其减去。当d为偶数时，反之亦然。以下是2D示例（来自SAT维基百科页面）
具有最高总和的子矩阵是最大和子矩阵。
使用Kadane算法可以将内部两个循环（起始索引和其中一个维度的子矩阵大小）减少为一个，使其为O(n^(2d-1))。
- samgak
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接