力扣刷题HOT100——53.最大子数组和

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

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

示例 1：

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

思路：

1. 初始化：

   • currentSum 初始化为 nums[0]，它代表以当前元素结尾的最大子数组和。
   • maxSum 也初始化为 nums[0]，用于记录全局最大子数组和。

2. 遍历数组：

   • 从数组的第二个元素开始遍历，对于每个元素 nums[i]，更新 currentSum 为 nums[i] 和 currentSum + nums[i] 中的较大值。这一步的含义是，如果当前元素本身比之前的子数组和加上当前元素还要大，那么就从当前元素开始一个新的子数组。
   • 接着更新 maxSum 为 maxSum 和 currentSum 中的较大值，以此保证 maxSum 始终记录着全局最大子数组和。

如图：

class Solution {
public:int maxSubArray(vector<int>& nums) {int currentSum = nums[0];int maxSum = nums[0];for (int i = 1; i < nums.size(); ++i) {currentSum = std::max(nums[i], currentSum + nums[i]);maxSum = std::max(maxSum, currentSum);}return maxSum;}
};

复杂度分析

• 时间复杂度：\(O(n)\)，这里的 n 是数组 nums 的长度，因为只需要遍历数组一次。
• 空间复杂度：\(O(1)\)，只使用了常数级的额外空间。