普通数组-53. 最大子数组和

文章目录1.题解一、问题本质二、核心算法Kadane 算法动态规划思想1. 核心思想一句话记住2. 为什么这个逻辑成立三、代码逐行拆解四、时间 空间复杂度五、好记的背诵版要点六、补充动态规划标准写法和你的代码等价2.机考代码3.知识点讲解Kadane 算法卡丹算法力扣地址 中等53. 最大子数组和挺简单的1.题解一、问题本质给一个整数数组找连续的一段子数组让它的和最大返回这个最大和。核心约束子数组必须连续不能跳着选且最少包含 1 个元素。示例[-2,1,-3,4,-1,2,1,-5,4]最大和是[4,-1,2,1]的和6。二、核心算法Kadane 算法动态规划思想1. 核心思想一句话记住“前面的和如果是正的就带着它如果是负的就直接从当前数重新开始”本质是动态规划dp[i]表示以第i个元素结尾的最大子数组和状态转移方程dp[i] max(nums[i], dp[i-1] nums[i])解释要么从当前数重新开始nums[i]要么把当前数接在前面的最大子数组后面dp[i-1]nums[i]选更大的那个最终答案所有dp[i]中的最大值2. 为什么这个逻辑成立如果前面的累加和curSum 0说明它对当前数有增益带着它能让当前子数组和更大所以直接加如果前面的累加和curSum ≤ 0说明它对当前数是拖累带着它只会让和变小不如直接从当前数重新开始每一步都记录全局最大值res最终就是答案三、代码逐行拆解classSolution{publicintmaxSubArray(int[]nums){// 初始化以第0个元素结尾的最大和就是nums[0]全局最大和也初始化为nums[0]intresnums[0];intcurSumnums[0];// 从第1个元素开始遍历for(inti1;inums.length;i){// 核心逻辑前面的和是正的就带着否则从当前数重新开始if(curSum0){curSumnums[i];}else{curSumnums[i];}// 更新全局最大和resMath.max(res,curSum);}returnres;}}四、时间 空间复杂度时间复杂度O(n)只遍历数组 1 次最优时间复杂度空间复杂度O(1)只用了 2 个变量原地计算最优空间复杂度五、好记的背诵版要点初始化res和curSum都等于数组第一个元素处理全负数的情况遍历逻辑curSum0就加当前数否则curSum等于当前数更新全局每一步用Math.max(res, curSum)更新最大和返回结果遍历结束后返回res六、补充动态规划标准写法和你的代码等价如果用标准 DP 数组写逻辑完全一致只是空间复杂度O(n)你的代码是空间优化后的版本publicintmaxSubArray(int[]nums){int[]dpnewint[nums.length];dp[0]nums[0];intresnums[0];for(inti1;inums.length;i){dp[i]Math.max(nums[i],dp[i-1]nums[i]);resMath.max(res,dp[i]);}returnres;}你的代码用curSum代替了dp[i-1]因为只需要前一个状态不需要整个数组是 Kadane 算法的标准优化写法。2.机考代码importjava.util.Scanner;publicclassMain{publicstaticintmaxSubArray(int[]nums){// 初始化以第0个元素结尾的最大和就是nums[0]全局最大和也初始化为nums[0]intresnums[0];intcurSumnums[0];// 从第1个元素开始遍历for(inti1;inums.length;i){// 核心逻辑前面的和是正的就带着否则从当前数重新开始if(curSum0){curSumnums[i];}else{curSumnums[i];}// 更新全局最大和resMath.max(res,curSum);}returnres;}publicstaticvoidmain(String[]args){ScannerscnewScanner(System.in);// 输入格式第一行输入数组长度第二行输入数组元素intnsc.nextInt();int[]numsnewint[n];for(inti0;in;i){nums[i]sc.nextInt();}// 调用方法并输出结果System.out.println(maxSubArray(nums));}}3.知识点讲解Kadane 算法卡丹算法Kadane 算法本质上就是「最大子数组和」问题的动态规划DP优化版本 是动态规划思想的经典应用。