13. 最大子数组和

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

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

方法一：动态规划

遍历right时，已经知道了以right-1结尾的最大子数组和cur_sum。

以right结尾的最大子数组和，有两种可能：

• 将nums[right]拼接到之前的子数组后面：cur_sum + nums[right]

• 放弃之前的子数组，重新开始一个子数组（只包含nums[right]自己）：nums[right]

class Solution(object): def maxSubArray(self, nums): max_sum=-float("inf") cur_sum=-float("inf") for right in range(len(nums)): if cur_sum+nums[right]<nums[right]: cur_sum=nums[right] else: cur_sum+=nums[right] if cur_sum>max_sum: max_sum=cur_sum return max_sum

方法二：分治法

对于一个区间 [l,r]，我们可以维护四个量：

lSum 表示 [l,r] 内以 l 为左端点的最大子段和
rSum 表示 [l,r] 内以 r 为右端点的最大子段和
mSum 表示 [l,r] 内的最大子段和
iSum 表示 [l,r] 的区间和——即为所求

class Solution(object): def get(self,nums,i,j): if i==j: return nums[i],nums[i],nums[i],nums[i] m=(i+j)//2 a=self.get(nums,i,m) b=self.get(nums,m+1,j) return a[0]+b[0],max(a[1],a[0]+b[1]),max(b[2],a[2]+b[0]),max(a[3],b[3],a[2]+b[1]) def maxSubArray(self, nums): return self.get(nums,0,len(nums)-1)[3]