最大子段和Kadane算法讲解一、问题定义给定一个整数数组找出一个连续、非空的子数组使得该子数组的元素和最大输出这个最大和。这是动态规划的经典入门题最优解法为Kadane 算法时间复杂度 O(n)空间复杂度 O(1)。二、算法原理与推导状态定义设dp[i]表示以第 i 个元素结尾的最大子段和。状态转移对于第 i 个元素有两种选择接在前面的子段后面和为dp[i-1] a[i]自己作为新子段的开头和为a[i]因此状态转移方程d p [ i ] max ⁡ ( a [ i ] , d p [ i − 1 ] a [ i ] ) dp[i] \max(a[i],\ dp[i-1] a[i])dp[i]max(a[i],dp[i−1]a[i])最终答案整个数组的最大子段和就是所有dp[i]中的最大值a n s max ⁡ ( d p [ 1 ] , d p [ 2 ] , . . . , d p [ n ] ) ans \max(dp[1],\ dp[2],\ ...,\ dp[n])ansmax(dp[1],dp[2],...,dp[n])空间优化因为计算dp[i]只需要dp[i-1]不需要保存整个 dp 数组只用一个变量记录当前结尾的最大子段和即可空间降到 O(1)。三、通用模板代码// 最大子段和模板Kadane算法intmaxSubArray(vectorintnums){intnnums.size();intcur_sumnums[0];// 以当前元素结尾的最大子段和intmax_sumnums[0];// 全局最大子段和for(inti1;in;i){cur_summax(nums[i],cur_sumnums[i]);max_summax(max_sum,cur_sum);}returnmax_sum;}同理最小子段和只需要把所有 max 换成 min 即可。四、模板题P1115 最大子段和 - 洛谷题目分析标准的最大子段和模板题直接套用 Kadane 算法即可。注意点数组元素可能全为负数此时答案就是最大的那个负数不能返回 0。你的代码解析#includebits/stdc.h#defineintlonglongusingnamespacestd;constintN2e59;intn,m,ans,sum;signedmain(){cinn;intx;cinx;sumansx;// 初始化第一个元素既是当前和也是全局最大for(inti2;in;i){cinx;// 核心转移延续前子段 / 开启新子段summax(sumx,x);// 更新全局最大值ansmax(ans,sum);}coutans;return0;}五、进阶练习题(洛谷26蓝桥杯国赛模拟赛原题P16683 盆栽 - 洛谷题目转化这道题是最大子段和的变形应用题解题关键是把原问题转化为最大/最小子段和模型。题意拆解初始所有花的美丽度总和为sum。选择一段区间[l,r]每个数异或 k总和的变化量 区间内每个数(a[i]^k) - a[i]的和。我们可以选择不浇水变化量为 0或者选一段区间浇水变化量为区间和。求最终总和的最小值和最大值。核心转化令b[i] (a[i] ^ k) - a[i]表示第 i 盆花浇水后的美丽度变化量。那么浇水能获得的最大总增益 数组 b 的最大子段和如果最大子段和为负就选择不浇水增益为 0浇水能获得的最小总增益 数组 b 的最小子段和如果最小子段和为正就选择不浇水增益为 0最终答案最小总和 sum min(最小子段和, 0)最大总和 sum max(最大子段和, 0)你的代码解析#includebits/stdc.h#defineintlonglongusingnamespacestd;constintN5010;intn,m,a[N],k,b[N],sum;signedmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cinnm;for(inti1;in;i){cina[i];suma[i];// 预处理初始总和}while(m--){cink;// 计算每个位置异或k后的变化量for(inti1;in;i){b[i](a[i]^k)-a[i];}// 同时求最小子段和 最大子段和intmi,mx,ansmi,ansmx;mimxb[1];ansmiansmxb[1];for(inti2;in;i){// 最小子段和转移mimin(b[i],mib[i]);// 最大子段和转移mxmax(b[i],mxb[i]);// 更新全局最值ansmimin(mi,ansmi);ansmxmax(mx,ansmx);}// 处理“可以不浇水”负增益才选最小正增益才选最大if(ansmi0)ansmisum;elseansmisum;if(ansmx0)ansmxsum;elseansmxsum;coutansmi ansmx\n;}return0;}复杂度分析每次查询 O(n)总时间 O(n×m)n 和 m 均为 5e3总运算量 2.5e7在时限内完全没问题。空间 O(n)用于存储增量数组 b。六、总结与拓展核心思想Kadane 算法的本质是线性 DP利用“以当前位置结尾”的状态定义实现 O(n) 的线性求解。常见变形最小子段和max 换 min环形最大子段和总和 - 最小子段和允许最多删除一个元素的最大子段和前后缀 DP区间修改后的最值子段和本题盆栽转化为增量数组的子段和易错提醒全负数情况不能返回 0必须选至少一个元素。注意数据范围子段和可能爆 int务必开 long long。