这个问题（最大子数组）的一维解决方案是 Theta(n)，使用一种名为“Kadane 算法”的算法（我确信还有其他算法，但我对此有个人经验）。使用 Kadane 算法的实现，该问题的 2D 解决方案（最大子矩形）已知为 O(n^3)（我再次确定还有其他算法，但我以前使用过这个算法）。
虽然我们知道 Theta(n^3) 可以找到二维解，但没有人能够证明 n^3 是否是下界。对于许多算法来说，当增加维度时，算法的下限就会增加一个常数值。对于这个特定的问题，复杂性不会线性增加，因此没有已知的解决方案适用于任何给定的维度，因此问题仍然悬而未决。
参考类似的情况：我们知道2个矩阵可以在n^3次内相乘。我相信还有一种算法可以在 n^2.8 中做到这一点。然而，没有数学表明我们不能让它低于 n^2.8，所以它仍然是一个“开放”算法。