【数据结构与算法】Kadane‘s算法（动态规划、最大子数组和）

一时失言乱红尘 2024-02-18 13:00 90阅读 0赞

#### 文章目录 ####

*  一、算法原理
 *  二、例题
 *   *  2.1 最大子数组和
     *  2.2 环形子数组的最大和

## 一、算法原理 ##

`Kadane's`算法是一种用于解决最大子数组和问题的动态规划算法。这类问题的目标是在给定整数数组中找到一个连续的子数组，使其元素之和最大（数组含有负数）。

算法的核心思想是通过迭代数组的每个元素，维护两个变量来跟踪局部最优解和全局最优解。

以下是Kadane’s算法的详细步骤：

1.  **初始化：**
    
     *  令 maxEndingHere 表示**在当前位置结束的最大子数组和**，初始值为数组的第一个元素。
     *  令 maxSoFar 表示**全局最大子数组和**，初始值也为数组的第一个元素。
2.  **迭代：**
    
     *  从数组的第二个元素开始迭代。
     *  对于每个元素，计算在当前位置结束的最大子数组和：  
        `maxEndingHere = max(nums[i], maxEndingHere + nums[i]);`  
        这表示要么继续当前子数组，要么从当前位置开始一个新的子数组。
     *  更新全局最大子数组和：  
        `maxSoFar = max(maxSoFar, maxEndingHere);`  
        如果在当前位置结束的子数组和大于全局最大和，更新全局最大和。
3.  **返回结果：**
    
     *  当迭代完成后，maxSoFar 中存储的即为最大子数组和。

**复杂度：**

*  时间复杂度：O(n)，其中 n 为 nums 数组的长度。我们只需要遍历一遍数组即可求得答案。
 *  空间复杂度：O(1)。我们只需要常数空间存放若干变量。

图例：  
![在这里插入图片描述][5a1d0f75c23940c8ac0b957e29401d8d.png]

简要说明：（如过**当前值**比前面的**局部最大值+当前值**还大，那么就从当前值开始继续计算局部最大值）

1.  i=0,maxEndingHere 、maxSoFar 初始值都为数组第一个元素，-2；
2.  开始循环，i=1，maxEndingHere = max(nums\[1\], maxEndingHere + nums\[1\])，即maxEndingHere = max(1, -2 + 1)=1，maxSoFar=1；
3.  i=2， maxEndingHere = max(nums\[2\], maxEndingHere + nums\[2\])，即maxEndingHere = max(-3, 1 - 3)=-2，maxSoFar=1；
4.  i=3，maxEndingHere = max(nums\[3\], maxEndingHere + nums\[3\])，即maxEndingHere = max(4, -2 + 4)=4，maxSoFar=4；
5.  …

## 二、例题 ##

### 2.1 最大子数组和 ###

![在这里插入图片描述][5216bfad7536476e813b0ed0768bd330.png]

解答：

int maxSubArray(int* nums, int numsSize) {
        
        int maxEndingHere  = nums[0], maxSoFar = nums[0];
        for (int i = 1; i < numsSize; i++) {
        
            maxEndingHere  = fmax(maxEndingHere  + nums[i], nums[i]);
            maxSoFar = fmax(maxSoFar, maxEndingHere );
        }
        return maxSoFar;
    }

> fmax是<math.h>中的函数，用于比较2个数字的大小，双精度。

简单换个写法：

int maxSubArray(int* nums, int numsSize) {
        
        int maxEndingHere  = nums[0], maxSoFar = nums[0];
        for (int i = 1; i < numsSize; i++) {
        
            maxEndingHere  = maxEndingHere  + nums[i]>nums[i]?maxEndingHere  + nums[i]:nums[i];
            maxSoFar = maxSoFar>maxEndingHere?maxSoFar:maxEndingHere;
        }
        return maxSoFar;
    }

> 简单用三目表达式代替fmax函数。

### 2.2 环形子数组的最大和 ###

![在这里插入图片描述][024bda1aa1ee44e9862c91b3b42bca58.png]

解答：

int maxSubarraySumCircular(int* nums, int numsSize) {
        
        if (nums == NULL || numsSize == 0) return 0;
        int maxSum = nums[0], minSum = nums[0];
        int maxCur = nums[0], minCur = nums[0];
        int sum = nums[0];
    
        for (int i = 1; i < numsSize; i++) {
        
            sum += nums[i];
            maxCur = fmax(nums[i], maxCur + nums[i]);
            minCur = fmin(nums[i], minCur + nums[i]);
            maxSum = fmax(maxSum, maxCur);
            minSum = fmin(minSum, minCur);
        }
    
        if (maxSum < 0) return maxSum; // 如果所有数都是负数，返回最大值
        return fmax(maxSum, sum - minSum); // 返回“不跨越头尾的最大子数组和”和“跨越头尾的最大子数组和”中的较大者
    }

[5a1d0f75c23940c8ac0b957e29401d8d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/c82642b02d804b3cae1ec6e12ffe84bc.png
[5216bfad7536476e813b0ed0768bd330.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/b92634c1d1d940ce96b0ea28ae51c57c.png
[024bda1aa1ee44e9862c91b3b42bca58.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/35b3a986bbeb4c91a492a4392f0496ff.png