4
假設你有一個N × N矩陣，其中每行只有一個非零元素，每列只有一個非零元素（非零元素可以是正面的也可以是負面的）。我們想要找到最大總和子矩陣。我們能如此有效地這樣做？子矩陣N×N矩陣和N非零值的最大和，只有O（N^2）
矩陣的維數爲N × N且只有N個非零元素。 N很大，所以我不能使用O（N ）算法。有沒有人知道如何及時解決這個問題？（N ），O（N log N）還是像這樣的其他時間複雜度？
謝謝！
A
回答
2
如果要查找最大總和子矩形，可以使用此處描述的算法maximum sum subrectangle in a sparse matrix在O（n^2 log n）時間內完成。這打敗了Kadane的算法，即O（n^3）。
相關問題
- 1. deteminant N * N矩陣
- 2. 插入和移位矩陣n * n
- 3. 新矩陣[N] [N]失敗
- 4. 如何從n維矩陣得到n維二維子矩陣？
- 5. N * N矩陣，計數唯一矩形矩陣的數量。
- 6. 在O（n^2）中尋找一個最大可能總和的子矩陣
- 7. 分矩陣爲n個矩陣
- 8. 如何矩陣矩陣轉換（N）（1，N）基體在python
- 9. 要將m×n矩陣轉換爲1×n矩陣
- 10. 如何通過n矩陣每n由M矩陣
- 11. N乘N矩陣的對角差
- 12. n-n矩陣作業分配
- 13. 尋找零的第一行的n×n矩陣用C
- 14. 爲N×M矩陣穿越
- 15. 從矩陣n×m個
- 16. n維矩陣乘法python
- 17. 查找m×n矩陣
- 18. 用（M，N）的右手大小矩陣
- 19. 隨機m×n矩陣的randperm子集
- 20. MATLAB：定義矩陣的n個子集
- 21. 證明最大（O（f（n）），O（g（n）））= O（max（f（n），g（n））
- 22. 使用高階函數的N * N大小的標識矩陣
- 23. C＃：在N×N矩陣中尋找最大m個元素的有效算法
- 24. 添加矩陣n維陣列
- 25. 用n個元素填充一個n * n矩陣
- 26. python協方差矩陣返回一個2N，2N矩陣而不是N，N？
- 27. 在N * N矩陣中的所有可能的路徑 - 蟒蛇
- 28. 爲什麼我得到兩個不同的反矩陣對於在N中增加的N * N矩陣？
- 29. n的方陣（N * N）
- 30. 提取矩陣中行r和列n-1處的值R
什麼是「微不足道的情況」？ – Matt
我假設N個非零元素的位置是未知的（不是稀疏矩陣），並且這些值都是正數和負數？ – IdeaHat
如果你不使用稀疏矩陣，那麼O（N^2）是最好的，因爲你至少必須讀取每個元素。可能將卡丹的算法推廣到二維。 http://stackoverflow.com/questions/12339280/find-max-sum-of-elements-in-array – Adam