【普通数组】LC 53.最大子数组和

文章目录前言一、题目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(n²)时间复杂度枚举所有子数组。分治法O(n log n)时间复杂度将问题分解为左半部分、右半部分和跨越中点的子数组。Kadane算法O(n)时间复杂度是最优解。相关 LeetCode 例题53. 最大子数组和本题152. 乘积最大子数组类似思路但需要考虑正负号918. 环形子数组的最大和Kadane算法的环形变体363. 矩形区域不超过 K 的最大数值和二维扩展难度较高