题目
53. Maximum Subarray
解法
方法一
curSum为包含当前值的连续序列最大值，如对序列nums[:i]，curSum和中必定包含nums[i]。
def maxSubArray(self, nums):
curSum = maxSum = nums[0]
for num in nums[1:]:
curSum = max(num, curSum + num)
maxSum = max(maxSum, curSum)
return maxSum
思路相同，另一种更为简洁的写法
def maxSubArray(self, nums: List[int]) -> int:
for i in range(1, len(nums)):
if nums[i-1] > 0:
nums[i] += nums[i-1]
return max(nums)
方法二
序列nums[k]可分为nums[0,1,...,s-1,s]和nums[s+1,s+2,...k-2,k-1]两部分。
我们可以轻易求出前半部分nums[:s]的值，则后部分nums[s+1:k]=nums[:k]-nums[:s]。
def maxSubArray(self, nums) -> int:
res = nums[0]
msub = min(nums[0], 0)
for i in range(1, len(nums)):
new = nums[i - 1] + nums[i]
res = max(new - msub, res, nums[i])
msub = min(new, msub)
nums[i] = new
return res
