题目大意
由 N 个整数元素组成的一维数组 (A[0], A[1],…,A[n-1], A[n])，这个数组有很多连续子数组，那么其中数组之和的最大值是什么呢？
子数组必须是连续的。 不需要返回子数组的具体位置。 数组中包含：正整数，零，负整数。
解题思路
Kadane Algorithm
官方标签为动态规划，这种算不算正经动态规划待定。 可以理解为：
dp[i] = dp[i-1] + s[i] (dp[i-1] >= 0) dp[i] = s[i] (dp[i-1] < 0) 复制代码
一旦前面总和<0,说明前面的加进去也是没用的，所以全部抛弃
list -2 1 -3 4 -1 2 1 -5 4 current -2 1 0 4 3 5 6 1 5 m -2 1 1 4 4 5 6 6 6 复制代码
动态规划
class Solution(object): def maxSubArray(self, nums): """ :type nums: List[int] :rtype: int """ if not nums: return 0 dp = [nums[0] for i in range(len(nums))] max_result = nums[0] # 最开始的是nums[0]，后面如果是负数肯定更小，如果是整数肯定变大 for i in range(1, len(nums)): if dp[i-1] < 0: dp[i] = nums[i] else: dp[i] = dp[i-1] + nums[i] if max_result < dp[i]: max_result = dp[i] return max_result 复制代码
直接方法
class Solution(object): def maxSubArray(self, nums): """ :type nums: List[int] :rtype: int """ if not nums: return 0 current = nums[0] m = current for i in range(1, len(nums)): if current < 0: current = 0 current += nums[i] m = max(current, m) return m 复制代码
分治法
对于任何一个array来说，有三种可能： 1。它的maximum subarray 落在它的左边； 2。maximum subarray 落在它的右边； 3。maximum subarray 落在它的中间。
对于第一，二种情况，利用二分法就很容易得到，base case 是如果只有一个数字了，那么就返回。
对于第三种情况，如果落在中间，那么我们要从左右两边返回的两个 mss 中，挑出一个大的，再从 （左右中大的值） 和 （左+右）中挑出一个大的
而且对于左半部分或者右半部分，上述结论也成立，利用这特性，可以写出相应的递归，递归结束的条件是当只有一个元素时，判断这个元素是否大于零，大于零便返回这个数，否则返回零。 然后求出左边最大值，右边最大值和横跨两边的最大值，返回这三个值中的最大值
class Solution(object): def maxSubArrayHelper(self,nums, l, r): if l > r: return -2147483647 m = (l+r) / 2 leftMax = sumNum = 0 for i in range(m - 1, l - 1, -1): # 从中间向左遍历 sumNum += nums[i] leftMax = max(leftMax, sumNum) rightMax = sumNum = 0 for i in range(m + 1, r + 1): # 从中间向右遍历 sumNum += nums[i] rightMax = max(rightMax, sumNum) leftAns = self.maxSubArrayHelper(nums, l, m - 1) rightAns = self.maxSubArrayHelper(nums, m + 1, r) return max(leftMax + nums[m] + rightMax, max(leftAns, rightAns)) # 返回三个中的最大值 def maxSubArray(self, nums): return self.maxSubArrayHelper(nums, 0, len(nums) - 1)
