最大二维子集和
我的任务是编写一个算法来计算整数矩阵的最大二维子集。 - 但是我对这种算法的帮助不感兴趣，我更感兴趣的是了解可能解决这个问题的最佳最坏情况的复杂性。
我们当前的算法类似于 O(n^3)。
我一直在考虑类似分而治之的方法，通过将矩阵拆分为多个子矩阵，只需将矩阵内的元素相加即可；从而限制了为了找到近似解而必须考虑的矩阵数量。
I'm given a task to write an algorithm to compute the maximum two dimensional subset, of a matrix of integers. - However I'm not interested in help for such an algorithm, I'm more interested in knowing the complexity for the best worse-case that can possibly solve this.
Our current algorithm is like O(n^3).
I've been considering, something alike divide and conquer, by splitting the matrix into a number of sub-matrices, simply by adding up the elements within the matrices; and thereby limiting the number of matrices one have to consider in order to find an approximate solution.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
最坏的情况（穷举搜索）绝对不比 O(n^3)更坏。网络上对此有多种描述。
最好的情况可能要好得多：O(1)。如果所有元素都是非负的，那么答案就是矩阵本身。如果元素为非正数，则答案是其值最接近零的元素。
同样，如果矩阵边缘上的整行/列只不过是非正整数，您可以在搜索中将它们切掉。
Worst case (exhaustive search) is definitely no worse than O(n^3). There are several descriptions of this on the web.
Best case can be far better: O(1). If all of the elements are non-negative, then the answer is the matrix itself. If the elements are non-positive, the answer is the element that has its value closest to zero.
Likewise if there are entire rows/columns on the edges of your matrix that are nothing but non-positive integers, you can chop these off in your search.
我认为没有更好的方法可以做到这一点。 - 至少人类还不知道。
我将坚持我得到的解决方案，主要是因为它很简单。
I've figured that there isn't a better way to do it. - At least not known to man yet.
And I'm going to stick with the solution I got, mainly because its simple.