未经博主同意，禁止瞎JB转载。
LeetCode53最大子序和
https://leetcode-cn.com/problems/maximum-subarray/description/
我的解法：
1 class Solution(object): 2 def maxSubArray(self, nums): 3 """ 4 :type nums: List[int] 5 :rtype: int 6 """ 7 sumer = 0 8 maxer = nums[0] 9 for i in nums:10 sumer += i11 if maxer < 0:12 maxer = max(maxer,i)13 else:14 maxer = max(maxer,sumer)15 if sumer<0:16 sumer = 017 return maxer
其实11-13行可以删除，变成：
1 class Solution(object): 2 def maxSubArray(self, nums): 3 """ 4 :type nums: List[int] 5 :rtype: int 6 """ 7 sumer = 0 8 maxer = nums[0] 9 for i in nums:10 sumer += i11 maxer = max(maxer,sumer)12 if sumer<0:13 sumer = 014 return maxer
更好的解决方案参考：
https://blog.csdn.net/weixin_41958153/article/details/81131379
动态规划：
1 class Solution: 2 3 4 def maxSubArray(self, nums): 5 """ 6 :type nums: List[int] 7 :rtype: int 8 """ 9 length=len(nums) 10 for i in range(1,length): 11 #当前值的大小与前面的值之和比较，若当前值更大，则取当前值，舍弃前面的值之和 12 subMaxSum=max(nums[i]+nums[i-1],nums[i]) 13 nums[i]=subMaxSum#将当前和最大的赋给nums[i]，新的nums存储的为和值 14 return max(nums)
分而治之：
1 class Solution(object): 2 def maxSubArray(self, nums): 3 #主函数 4 left = 0 5 #左右边界 6 right = len(nums)-1 7 #求最大和 8 maxSum = self.divide(nums,left,right) 9 return maxSum10 11 def divide(self,nums,left,right):12 #如果只有一个元素就返回13 if left==right:14 return nums[left]15 #确立中心点16 center = (left+right)//217 #求子序在中心点左边的和18 leftMaxSum = self.divide(nums,left,center)19 #求子序在中心点右边的和20 rightMaxSum = self.divide(nums,center+1,right)21 22 #求子序横跨2边的和，分成左边界和和右边界和23 leftBorderSum = nums[center]24 leftSum = nums[center]25 for i in range(center-1,left-1,-1):26 leftSum += nums[i]27 if leftSum>leftBorderSum:28 #不断更新左区块的最大值29 leftBorderSum = leftSum30 31 rightBorderSum = nums[center+1]32 rightSum = nums[center+1]33 for i in range(center+2,right+1):34 rightSum += nums[i]35 if rightSum>rightBorderSum:36 #不断更新右区块的最大值37 rightBorderSum = rightSum38 #左边界的和 + 右边那块的和39 BorderSum = leftBorderSum + rightBorderSum40 return max(leftMaxSum,rightMaxSum,BorderSum)
个人认为分治法虽然分治法时间复杂度降到了O(nlogn)，但是代码复杂度较高，性价比在实现层面对于小数据集不高。