LeetCode热门100题-最大子数组和-错题

题目描述：

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组

是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

实现逻辑：

与上一题相似，都是求和为k的子数组，只不过上一题是k为一个确定值，而此题是求和为最大值。

那可以先求出数列{Sn}，再从Sn中找到一个最小值min，和在其右侧的某个最大数max，使得二者的差值最小。这又与后续一个贪心算法的题很相似，找到股票进账最多的买入天数和卖出天数。

class Solution { public: int maxSubArray(vector<int>& nums) { vector<int> Sn; // 存储前缀和 int current_sum = 0; Sn.push_back(current_sum); // 初始前缀和为0 // 计算所有前缀和并存入 Sn for (const int& num : nums) { current_sum += num; Sn.push_back(current_sum); } int Max = INT_MIN; // 初始化为最小可能值，以处理所有元素都是负数的情况 int min_prefix_sum = 0; // 用于跟踪到目前为止遇到的最小前缀和 // 遍历 Sn 来找到最大子数组和 for (int i = 1; i < Sn.size(); ++i) { // 从 1 开始，因为 Sn[0] 是初始前缀和 0 // 更新最大子数组和 Max = max(Max, Sn[i] - min_prefix_sum); // 更新最小前缀和 min_prefix_sum = min(min_prefix_sum, Sn[i]); } return Max; } };

 那么这个代码就是基于这样的一个逻辑去实现的。当然还有更高效的算法：

class Solution { public: int maxSubArray(vector<int>& nums) { // 初始化当前子数组的和和最大子数组和 int current_sum = nums[0]; // 当前子数组和 int max_sum = nums[0]; // 最大子数组和 // 从第二个元素开始遍历 for (int i = 1; i < nums.size(); ++i) { // 判断是否要从当前元素开始新的子数组，还是继续累加当前子数组 current_sum = max(nums[i], current_sum + nums[i]); // 更新最大子数组和 max_sum = max(max_sum, current_sum); } return max_sum; } };

 错题记录：

class Solution { public: int maxSubArray(vector<int>& nums) { int maxSum=nums[0]; int currentSum=nums[0]; for(int i=1;i<nums.size();i++) //注意 一开始给的i=0; { currentSum = max(nums[i],currentSum+nums[i]); maxSum = max(maxSum,currentSum); } return maxSum; } };