Maximum subArray

英文原题

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Follow up:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

中文原题

给定一个数组，找这个数组里具有最大和的连续子数组，并且返回对应的最大值
如果你找到了使用O(n)时间复杂度的解法，不妨也尝试以下使用分治法解题。

最优题解

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        for i in range(1, len(nums)):
            nums[i] = nums[i] + max(nums[i-1], 0)
        return max(nums)

这是一种动态规划思维，代码相当简洁，只有三行。解题思路大概是：

1. 遍历列表
2. nums[i] = nums[i] + max(nums[i-1])，这段代码需要注意的是, nums[i-1]并不是与数组前一项相加，而是到前一项为止的最大子序和，和0比较是因为只要大于0，就可以相加构造最大子序和，如果小于零则相加为0，nums[i] = nums[i]，相当于最大子序和归零，重新计算。

暴力题解

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        tmp = nums[0]
        max_ = tmp
        n = len(nums)
        for i in range(1, n):
            if tmp + nums[i] > nums[i]:
                max_ = max(max_, tmp+nums[i])
                tmp = tmp + nums[i]
            else:
                max_ = max(max_, tmp, tmp+nums[i], nums[i])
                tmp = nums[i]
        return max_