【leetcode复健-11】53. 最大子数组和-滑动窗口

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

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

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

示例 1：

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

示例 2：

输入：nums = [1]输出：1

示例 3：

输入：nums = [5,4,-1,7,8]输出：23

提示：

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104

题目分析

如果写过一些滑动窗口的题目就会发现，这题其实不难，想到了就能很快写出来。
给定一个数组，找出一个和最大的连续子数组
这题的关键在于判断子数组是否为有效数组，假设存在一组子数组，如果子数组为正，则该子数组对后续数组是有贡献的，如果非正，则该子数组对后续没有任何贡献，可以舍弃。
根据这个思路，我们可以从左往右遍历一遍数组，遍历的过程中不断累加当前值并判断是否要更新最大子数组，倘若当前累加值非正，则代表前面的数组对后续计算没有任何贡献，可以舍弃，更新当前数组起点。
此外由于这道题只要求我们返回数值，因此我们可以避免使用指针，使用 for 循环解决

代码思路

存两个变量max_sum、cur_sum保存最大和、当前和

for循环遍历

每次循环累加 cur_sum 的值，并时刻更新 max_sum ，当 当前遍历的元素大于cur_sum时，说明之前累加的数小于0，对之后的子数组无贡献，更新 cur_sum 变成当前元素。

一轮循环后即可找出最大子数组之和

正确代码

class Solution: def maxSubArray(self, nums: List[int]) -> int: max_sum = cur_sum = nums[0] for i in range(1, len(nums)): cur_sum = max(cur_sum + nums[i], nums[i]) max_sum = max(max_sum, cur_sum) return max_sum