Kadane算法 C++实现

算法通关之路一文吃透Kadane算法C实现在算法面试和日常刷题中最大子数组和Maximum Subarray是一道经典必考题。暴力枚举所有子数组的解法时间复杂度高达 O(n²)而今天要讲的Kadane算法卡登算法能以O(n) 时间复杂度 O(1) 空间复杂度完美解决这个问题简洁又高效。今天就用博客的形式带你从原理到C代码彻底掌握Kadane算法一、问题背景先明确问题给定一个整数数组包含正数、负数、0找到一个连续的子数组使其元素之和最大返回这个最大和。示例输入nums [-2,1,-3,4,-1,2,1,-5,4]输出6对应子数组[4,-1,2,1]暴力思路遍历所有起点和终点计算子数组和取最大值。但数组长度一大就会超时这时候Kadane算法就派上用场了。二、Kadane算法核心原理Kadane算法的核心思想只有一句话****每一步都做出当前最优选择最终得到全局最优解贪心思想。我们遍历数组时维护两个关键变量当前最大和current_max以当前元素为结尾的连续子数组的最大和。全局最大和global_max遍历过程中所有子数组的最大和最终答案。核心决策逻辑对于数组中的每一个元素nums[i]我们只有两种选择把nums[i]加入前面的子数组→current_max nums[i]以nums[i]作为新子数组的起点→nums[i]我们取两者的最大值作为新的current_max保证每一步都是当前最优。同时每次更新current_max后用它更新global_max记录全局最优。举个例子理解数组[-2,1,-3,4]初始current_max-2global_max-2元素1max(1, -21)1 →current_max1global_max1元素-3max(-3, 1(-3))-2 →current_max-2global_max1元素4max(4, -24)4 →current_max4global_max4三、算法步骤清晰版初始化current_max和global_max为数组第一个元素。从数组第二个元素开始遍历更新current_max max(nums[i], current_max nums[i])更新global_max max(global_max, current_max)遍历结束global_max就是答案。四、C 代码实现1. 基础版最简洁面试首选直接实现核心逻辑无多余操作时间O(n)空间O(1)#includeiostream#includevector#includealgorithm// 用于max函数usingnamespacestd;// Kadane算法求最大子数组和intmaxSubArray(vectorintnums){// 边界判断数组为空返回0根据题目要求调整if(nums.empty())return0;// 初始化当前最大和、全局最大和为第一个元素intcurrent_maxnums[0];intglobal_maxnums[0];// 从第二个元素开始遍历for(inti1;inums.size();i){// 核心当前最优选择current_maxmax(nums[i],current_maxnums[i]);// 更新全局最优global_maxmax(global_max,current_max);}returnglobal_max;}// 测试代码intmain(){vectorintnums{-2,1,-3,4,-1,2,1,-5,4};cout最大子数组和maxSubArray(nums)endl;// 输出6return0;}2. 进阶版记录最大子数组的下标如果题目不仅要求最大和还要求输出子数组的起始、结束下标可以在基础版上稍作修改#includeiostream#includevector#includealgorithmusingnamespacestd;intmaxSubArray(vectorintnums,intstart,intend){if(nums.empty())return0;intcurrent_maxnums[0];intglobal_maxnums[0];inttemp_start0;// 临时记录当前子数组的起点for(inti1;inums.size();i){// 选择重新开始更新临时起点if(nums[i]current_maxnums[i]){current_maxnums[i];temp_starti;}else{// 选择加入前面的子数组current_maxnums[i];}// 更新全局最大和记录最终起止下标if(current_maxglobal_max){global_maxcurrent_max;starttemp_start;endi;}}returnglobal_max;}// 测试代码intmain(){vectorintnums{-2,1,-3,4,-1,2,1,-5,4};intstart0,end0;intmax_summaxSubArray(nums,start,end);cout最大子数组和max_sumendl;cout子数组下标[start, end]endl;cout子数组;for(intistart;iend;i){coutnums[i] ;}return0;}输出结果最大子数组和6 子数组下标[3, 6] 子数组4 -1 2 1五、关键细节说明全负数数组Kadane算法依然有效比如数组[-5,-3,-2,-1]算法会返回最大的单个元素-1符合题意因为子数组至少包含一个元素。空间复杂度基础版只用到两个变量是最优空间复杂度无需额外开辟数组。适用场景除了经典的最大子数组和还能解决最大子矩阵和二维Kadane、环形数组最大子数组和等变形题。六、算法复杂度分析时间复杂度O(n) —— 只遍历数组一次无嵌套循环。空间复杂度O(1) —— 仅使用常数个变量不随数组长度变化。这也是Kadane算法成为最优解的原因七、总结Kadane算法是贪心思想的经典应用核心就是每一步只做最优选择要么延续前面的子数组要么重新开始新子数组。时间O(n) 空间O(1)是最大子数组和问题的最优解法。C实现简洁面试手写无压力还能轻松扩展记录子数组下标。掌握这个算法再也不怕最大子数组和相关的面试题啦核心要点回顾核心思想贪心每一步取当前最优延续/重启子数组关键变量current_max当前结尾最大和、global_max全局最大和复杂度O(n)时间O(1)空间适用场景最大子数组和及各类变形题