山东富泰建设工程有限公司网站,做网站为什么需要营业执照,电商运营培训班,微商货源类网站源码给你一个整数数组 nums #xff0c;请你找出一个具有最大和的连续子数组#xff08;子数组最少包含一个元素#xff09;#xff0c;返回其最大和。 子数组是数组中的一个连续部分。 示例 1#xff1a; 输入#xff1a;nums [-2,1,-3,4,-1,2,1,-5,4] 输出#xff1a;6 解… 给你一个整数数组 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 1 0 5 10^5 105 - 1 0 4 10^4 104 nums[i] 1 0 4 10^4 104 思路看leetcode官方视频讲解
class Solution:def maxSubArray(self, nums: list) - int:#贪心解法: 如果当前元素之前的和小于0那么就应该丢弃否则加上当前元素maxsum, presum -10000, -10000if len(nums) 1:return nums[0]for i in nums:if presum 0:presum ielse:presum imaxsum max(maxsum, presum)return maxsumdef maxSubArray(self, nums: list) - int:#动态规划如果前一个元素大于0把它加到当前元素上if len(nums) 1:return nums[0]maxsum nums[0]for i in range(1,len(nums)):nums[i] max(nums[i], nums[i] nums[i-1])maxsum max(nums[i], maxsum)return maxsum贪心解法在这道题上比较容易理解但也有一个点就是需要设着两个变量一个记录最大值一个记录当前的和。想一下前面一个连续数组的和很大但是遇到了一个更大的负数导致和小于等于0当重新开始计数后后边的数组和不一定比前面的大所以需要两个变量
