当前位置：首页 > news >正文

Kadane算法 C++实现

news 2026/5/29 21:12:57

算法通关之路：一文吃透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=-2，global_max=-2
元素1：max(1, -2+1)=1 →current_max=1，global_max=1
元素-3：max(-3, 1+(-3))=-2 →current_max=-2，global_max=1
元素4：max(4, -2+4)=4 →current_max=4，global_max=4

三、算法步骤（清晰版）

初始化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)：

#include<iostream>#include<vector>#include<algorithm>// 用于max函数usingnamespacestd;// Kadane算法：求最大子数组和intmaxSubArray(vector<int>&nums){// 边界判断：数组为空返回0（根据题目要求调整）if(nums.empty())return0;// 初始化当前最大和、全局最大和为第一个元素intcurrent_max=nums[0];intglobal_max=nums[0];// 从第二个元素开始遍历for(inti=1;i<nums.size();++i){// 核心：当前最优选择current_max=max(nums[i],current_max+nums[i]);// 更新全局最优global_max=max(global_max,current_max);}returnglobal_max;}// 测试代码intmain(){vector<int>nums={-2,1,-3,4,-1,2,1,-5,4};cout<<"最大子数组和："<<maxSubArray(nums)<<endl;// 输出6return0;}

2. 进阶版：记录最大子数组的下标

如果题目不仅要求最大和，还要求输出子数组的起始、结束下标，可以在基础版上稍作修改：

#include<iostream>#include<vector>#include<algorithm>usingnamespacestd;intmaxSubArray(vector<int>&nums,int&start,int&end){if(nums.empty())return0;intcurrent_max=nums[0];intglobal_max=nums[0];inttemp_start=0;// 临时记录当前子数组的起点for(inti=1;i<nums.size();++i){// 选择重新开始：更新临时起点if(nums[i]>current_max+nums[i]){current_max=nums[i];temp_start=i;}else{// 选择加入前面的子数组current_max+=nums[i];}// 更新全局最大和，记录最终起止下标if(current_max>global_max){global_max=current_max;start=temp_start;end=i;}}returnglobal_max;}// 测试代码intmain(){vector<int>nums={-2,1,-3,4,-1,2,1,-5,4};intstart=0,end=0;intmax_sum=maxSubArray(nums,start,end);cout<<"最大子数组和："<<max_sum<<endl;cout<<"子数组下标：["<<start<<", "<<end<<"]"<<endl;cout<<"子数组：";for(inti=start;i<=end;++i){cout<<nums[i]<<" ";}return0;}

输出结果：

最大子数组和：6 子数组下标：[3, 6] 子数组：4 -1 2 1

五、关键细节说明

全负数数组：Kadane算法依然有效！比如数组[-5,-3,-2,-1]，算法会返回最大的单个元素-1（符合题意，因为子数组至少包含一个元素）。
空间复杂度：基础版只用到两个变量，是最优空间复杂度，无需额外开辟数组。
适用场景：除了经典的最大子数组和，还能解决最大子矩阵和（二维Kadane）、环形数组最大子数组和等变形题。