給定一個(gè)正整數(shù)和負(fù)整數(shù)組成的N by N matrix, 找出元素總和最大的sub matrix. ?Page 306.
超級(jí)難
最暴力的解法： O(N^6)
直接迭代所有可能的子矩陣。要迭代的子矩陣為O(N^4) 計(jì)算每個(gè)sub matrix總和時(shí)間O(N^2).所以復(fù)雜度O(N^6)
Better: DP: O(N^4)
Optimal: O(N^3)
Sum最大子矩陣[難]
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。
相關(guān)閱讀更多精彩內(nèi)容
- 背景 一年多以前我在知乎上答了有關(guān)LeetCode的問題, 分享了一些自己做題目的經(jīng)驗(yàn)。 張土汪：刷leetcod...
- 算法和數(shù)據(jù)結(jié)構(gòu) [TOC] 算法 函數(shù)的增長 漸近記號(hào) 用來描述算法漸近運(yùn)行時(shí)間的記號(hào)，根據(jù)定義域?yàn)樽匀粩?shù)集$N=...
- 第一次讀蔣勛的文，是他的《說紅樓夢(mèng)》。 很仔細(xì)地帶我們讀，每一章每一回，仔細(xì)地分析他們的情感和故事走向。當(dāng)我看完那...
- 三尺童子，一介書生，忽智忽愚，且貧且病，屠龍有術(shù)，縛雞無力，或鉤或劍，可屈可伸。我比拿破倫個(gè)子矮，同魯迅曹禺相當(dāng)，...
