怎么自己做网站服务器,湖北seo推广系统,网页设计大作业,晋江企业网站建设题目#xff1a; 给你一个整数数组 nums #xff0c;请你找出一个具有最大和的连续子数组#xff08;子数组最少包含一个元素#xff09;#xff0c;返回其最大和。 子数组 是数组中的一个连续部分。 来源#xff1a;力扣#xff08;LeetCode#xff09; 链接#xff… 题目 给你一个整数数组 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
