文章目錄前言一、題目1、原題鏈接2、題目描述二、個(gè)人思路整理1、思路分析2、解題代碼未優(yōu)化空間復(fù)雜度代碼優(yōu)化空間復(fù)雜度代碼三、知識(shí)風(fēng)暴前言本專(zhuān)欄文章為《LeetCode 熱題 100》的刷題題解相關(guān)內(nèi)容如有侵權(quán)立即刪除。一、題目1、原題鏈接53.最大子數(shù)組和2、題目描述二、個(gè)人思路整理1、思路分析核心思路動(dòng)態(tài)規(guī)劃Kadane算法狀態(tài)定義設(shè)dp[i]表示以nums[i]結(jié)尾的連續(xù)子數(shù)組的最大和。轉(zhuǎn)移方程d p [ i ] max ? ( d p [ i ? 1 ] n u m s [ i ] , n u m s [ i ] ) dp[i] \max(dp[i - 1] nums[i], nums[i])dp[i]max(dp[i?1]nums[i],nums[i])若前面的累加和d p [ i ? 1 ] 0 dp[i-1] 0dp[i?1]0加上當(dāng)前值有增益若d p [ i ? 1 ] ≤ 0 dp[i-1] \le 0dp[i?1]≤0前面的和只會(huì)拖累當(dāng)前值直接從n u m s [ i ] nums[i]nums[i]重新開(kāi)始?？臻g優(yōu)化因?yàn)閐p[i]只與dp[i-1]有關(guān)可用一個(gè)變量cur_sum滾動(dòng)維護(hù)將空間復(fù)雜度降至O ( 1 ) O(1)O(1)。2、解題代碼未優(yōu)化空間復(fù)雜度代碼classSolution{public:intmaxSubArray(vectorintnums){vectorintdp(nums.size());// 初始化以nums[0]結(jié)尾的子數(shù)組只有nums[0]本身dp[0]nums[0];// 記錄遍歷過(guò)程中出現(xiàn)的全局最大子數(shù)組和intansdp[0];for(inti1;inums.size();i){dp[i]max(dp[i-1]nums[i],nums[i]);// 每推導(dǎo)出一個(gè)dp[i]就嘗試更新全局最大值// 注意最終答案不一定是dp[nums.size() -1]而是整個(gè)dp數(shù)組中的最大值ansmax(ans,dp[i]);}returnans;}};復(fù)雜度分析時(shí)間復(fù)雜度O ( n ) O(n)O(n)只需單層 for 循環(huán)線性掃描一次數(shù)組?？臻g復(fù)雜度O ( n ) O(n)O(n)顯式創(chuàng)建了長(zhǎng)度為n nn的 dp 數(shù)組存儲(chǔ)中間狀態(tài)。優(yōu)化空間復(fù)雜度代碼classSolution{public:intmaxSubArray(vectorintnums){intmax_sumnums[0];intcur_sumnums[0];for(inti1;inums.size();i){cur_summax(nums[i],cur_sumnums[i]);max_summax(max_sum,cur_sum);}returnmax_sum;}};復(fù)雜度分析時(shí)間復(fù)雜度O ( n ) O(n)O(n)只需單層 for 循環(huán)線性掃描一次數(shù)組。空間復(fù)雜度O ( 1 ) O(1)O(1)兩個(gè)int變量空間。三、知識(shí)風(fēng)暴Kadane算法是解決最大子數(shù)組和問(wèn)題的經(jīng)典動(dòng)態(tài)規(guī)劃算法由計(jì)算機(jī)科學(xué)家Jay Kadane于1984年提出。該算法以其簡(jiǎn)潔高效著稱(chēng)時(shí)間復(fù)雜度為O(n)空間復(fù)雜度可優(yōu)化至O(1)。算法核心思想局部最優(yōu)與全局最優(yōu)Kadane算法的核心是維護(hù)兩個(gè)變量cur_sum以當(dāng)前位置結(jié)尾的最大子數(shù)組和局部最優(yōu)max_sum遍歷過(guò)程中遇到的最大子數(shù)組和全局最優(yōu)貪心選擇對(duì)于每個(gè)元素nums[i]要么將其加入前面的子數(shù)組cur_sum nums[i]要么從它開(kāi)始新的子數(shù)組nums[i]取兩者中的較大值作為新的cur_sum。狀態(tài)轉(zhuǎn)移cur_sum max(nums[i], cur_sum nums[i])算法變體與擴(kuò)展返回子數(shù)組位置修改算法以記錄最大子數(shù)組的起始和結(jié)束索引。處理全負(fù)數(shù)數(shù)組標(biāo)準(zhǔn)Kadane算法能正確處理全負(fù)數(shù)數(shù)組返回最大的單個(gè)負(fù)數(shù)。環(huán)形數(shù)組最大子數(shù)組和通過(guò)分析兩種情況不跨越邊界和跨越邊界來(lái)解決。二維矩陣最大子矩陣和通過(guò)壓縮行轉(zhuǎn)化為一維問(wèn)題再應(yīng)用Kadane算法。與其他算法的對(duì)比暴力法O(n2)時(shí)間復(fù)雜度枚舉所有子數(shù)組。分治法O(n log n)時(shí)間復(fù)雜度將問(wèn)題分解為左半部分、右半部分和跨越中點(diǎn)的子數(shù)組。Kadane算法O(n)時(shí)間復(fù)雜度是最優(yōu)解。相關(guān) LeetCode 例題53. 最大子數(shù)組和本題152. 乘積最大子數(shù)組類(lèi)似思路但需要考慮正負(fù)號(hào)918. 環(huán)形子數(shù)組的最大和Kadane算法的環(huán)形變體363. 矩形區(qū)域不超過(guò) K 的最大數(shù)值和二維擴(kuò)展難度較高