complexity-theory - 最大二维子集和

Question

我的任务是编写一个算法来计算整数矩阵的最大二维子集。- 但是我对这种算法的帮助不感兴趣，我更感兴趣的是了解可能解决这个问题的最坏情况的复杂性。

我们当前的算法就像 O(n^3)。

我一直在考虑类似分而治之的事情，通过将矩阵拆分为多个子矩阵，只需将矩阵中的元素相加即可；从而限制了为了找到近似解而必须考虑的矩阵的数量。

Answer 1

最坏情况（穷举搜索）绝对不比O(n^3) 差。网上对此有多种描述。

最好的情况会好得多：O(1)。如果所有元素都是非负的，那么答案就是矩阵本身。如果元素为非正数，则答案是其值最接近零的元素。

同样，如果矩阵边缘的整行/列都是非正整数，则可以在搜索中将其删除。

Answer 2

我认为没有更好的方法可以做到这一点。- 至少人类还不知道。我会坚持我得到的解决方案，主要是因为它很简单。