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