LeetCode - 53. 最大子数组和

目录

题目

Kadane 算法核心思想

Kadane 算法的步骤分析

读者可能的错误写法

正确的写法

题目

53. 最大子数组和 - 力扣（LeetCode）

Kadane 算法核心思想

定义状态变量:

• currentSum: 表示以当前元素为结束的子数组的最大和。

• maxSum: 记录全局最大子数组和。

动态规划转移方程:

对于数组中的每个元素 nums[i]:

• 如果 currentSum + nums[i] > nums[i]，则将当前元素加到之前的子数组中（即扩展子数组）。

• 如果 currentSum + nums[i] <= nums[i]，则重新开始一个新的子数组，从 nums[i] 开始。

• 转移方程: currentSum = max(currentSum + nums[i], nums[i])

更新全局最大值:

• 在每一步计算中，比较 currentSum 和 maxSum，更新全局最大值: maxSum = max(maxSum, currentSum)

时间复杂度:

• 遍历一次数组，时间复杂度为 O(n)。

• 空间复杂度为 O(1)，只需常量空间记录 currentSum 和 maxSum。

Kadane 算法的步骤分析

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]

最终结果：maxSum = 6，对应子数组 [4, -1, 2, 1]。 

读者可能的错误写法

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int currenSum = 0;
        int maxSum = 0;

        for(int i =0;i<nums.size();i++)
        {
            currenSum += nums[i];

            if(nums[i] > maxSum)
            {
                maxSum = nums[i];
            }
        }

        return currenSum;
    }
};

逻辑错误：这个的代码没有正确实现Kadane算法。你只是在累加所有元素（currenSum                 += nums[i]），这计算的是整个数组的和，而不是最大子数组和。

maxSum初始化错误：应该初始化为数组的第一个元素，而不是0（因为数组可能全为负数）。

比较错误：你在比较nums[i]和maxSum，但应该比较currenSum和maxSum。

没有实现核心逻辑：没有实现"选择继续当前子数组还是开始新子数组"的逻辑。

你在最后返回的是currenSum而不是maxSum：currenSum是以最后一个元素结尾的子数组的最大和，但这不一定是整个数组中的最大子数组和。

正确的返回值应该是maxSum，因为它记录了遍历过程中找到的全局最大子数组和。

正确的写法

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int currenSum = nums[0];
        int maxSum = nums[0];

        for(int i =1;i<nums.size();i++)
        {
           currenSum = max(currenSum+nums[i],nums[i]);
            maxSum = max(maxSum,currenSum);
        }

        return maxSum;
    }
};