力扣：53. 最大子数组和（Python3）

题目：

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

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

来源：力扣（LeetCode）
链接：力扣

示例：

示例 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

解法：

首先去除nums头尾的非正数，因为头尾非正数是连累项。接着对nums中间的的数，把连续的正数相加，把连续的负数相加，把0去掉。因为连续的正数可以使最大子数组更大，应该捆绑，连续的负数相加是因为只加单个负数只会拖累结果，如果要加负数是因为在负数后面有更大的正数使结果更大，但要加到后面的正数，那么之前的负数也要连续相加，0没有意义可以去掉。这样nums变成正数负数相隔的排列。然后遍历每个正数（外层循环），试探当前正数加上后面紧跟的负数和正数有没有使结果更大，2个2个向后试探（内层循环），因为也许加上当前会使结果变小，但继续往后加又可以使结果变大，但为了加到后面大的，前面的也要相加。如果只写成这样，是过不了的，因为超时了，所以对内层循环可以有些优化。当目前累加值小于等于0可以提前终止，这说明从这个正数开始的连续子串只会减小后面的数，还不如从后面的正数开始。

代码：

class Solution:def maxSubArray(self, nums: List[int]) -> int:left = 0for num in nums:if num <= 0:left += 1else:breakright = len(nums)for num in nums[::-1]:if num <= 0:right -= 1else:breakif left != len(nums) and right != 0:nums = nums[left:right]else:return max(nums)if len(nums) == 1:return nums[0]new = nums[0]new_nums = []nums = [num for num in nums if num != 0]for index, num in enumerate(nums[:-1]):if num * nums[index + 1] >= 0:new += nums[index + 1]else:new_nums.append(new)new = nums[index + 1]new_nums.append(new)result = new_nums[0]for index1, num1 in enumerate(new_nums[::2]):cal = num1result = cal if cal > result else resultif 2 * index1 + 1 >= len(new_nums) - 1:return result if result >= cal else calfor index2 in range(2 * index1, len(new_nums) - 1, 2):cal += new_nums[index2 + 2] + new_nums[index2 + 1]if cal <= 0:breakresult = cal if cal > result else result