最大的二維子集和總和

Question

我給了一個任務來編寫一個算法來計算整數矩陣的最大二維子集。 - 但是我對這樣一種算法的幫助不感興趣，我更感興趣的是知道可能解決這個問題的最糟糕情況的複雜性。

我們現在的算法就像O（n^3）。

我一直在考慮類似分而治之的方法，通過將矩陣分解成多個子矩陣，只需將矩陣中的元素相加即可;從而限制人們爲了找到近似解決方案而必須考慮的矩陣的數量。

Answer 1

我發現沒有更好的方法來做到這一點。 - 至少還不知道男人呢。 我將堅持使用我的解決方案，主要是因爲它簡單。

Answer 2

最壞情況（窮舉搜索）絕對不是差比O（n^3）。網絡上有幾種這樣的描述。 O（1）。最好的情況可以更好：O（1）。如果所有的元素都是非負的，那麼答案就是矩陣本身。如果元素是非正數，則答案是其值接近零的元素。

同樣，如果矩陣的邊緣上有整行/列都是非正整數，您可以在搜索時將它們切掉。