找到一个子矩阵以最大可能的总和在为O（n ^ 2） [英] Finding a submatrix with the maximum possible sum in O(n^2)

问题描述

我试图用Java编写一个程序，在给定的m×n矩阵，将找到的（相邻的）子矩阵与数字最大的总和。然后程序需要返回子矩阵的左上角的坐标和右下角的坐标。该基体可以包括负数和两个矩阵和子矩阵不必是正方形。

I'm trying to write a program in Java that when given an MxN matrix it will find the (contiguous) submatrix with the biggest sum of numbers. The program then needs to return the top left corner coordinates of the submatrix and the bottom right corner coordinates. The matrix can include negative numbers and both the matrix and submatrix don't need to be square.

我看到了，这是这里讨论：<一href="http://stackoverflow.com/questions/2643908/getting-the-submatrix-with-maximum-sum">http://stackoverflow.com/questions/2643908/getting-the-submatrix-with-maximum-sum并将该溶液似乎有为O（n ^ 3）。我的一个朋友说，他们曾设法解决o这个问题（N ^ 2）。也有人这里这可能吗？

I saw that this was discussed here: http://stackoverflow.com/questions/2643908/getting-the-submatrix-with-maximum-sum and the solution there seems to be O(n^3). A friend of mine said that they had once managed to solve this problem in O(n^2). Also suggested here. Is that possible?

有没有可用的code，在那里，解决这个问题最有效的方法是什么？

Is there any available code out there that solves this problem in the most efficient way?

推荐答案

您（最有可能）无法解决您的问题，为O（n ^ 2），在至少没有这样的算法是已知的。最佳的解决方案有子立方的复杂性，但它是非常难以实施，可能在实践中要慢。你可以阅读了一篇关于它这里。

You (most likely) can't solve your problem in O(n^2), at least no such algorithm is known. The optimal solution has sub-cubic complexity, but it's very hard to implement and probably slower in practice. You can read a paper about it here.

用通常的算法是为O（n ^ 3）之一，你发现了这个问题引用。

The usual algorithm used is the O(n^3) one referenced in the question you found.

这篇关于找到一个子矩阵以最大可能的总和在为O（n ^ 2）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！