【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