Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array[-2,1,-3,4,-1,2,1,-5,4], the contiguous subarray[4,-1,2,1]has the largest sum =6.

假设A(0, i)区间存在k，使得[k, i]区间是以i结尾区间的最大值， 定义为Max[i], 在这里，当求取Max[i+1]时，

Max[i+1] = Max[i] + A[i+1], if (Max[i] + A[i+1] >0)

            = 0, if\(Max\[i\]+A\[i+1\] <0\)，如果和小于零，A\[i+1\]必为负数，没必要保留，舍弃掉

然后从左往右扫描，求取Max数字的最大值即为所求

O(n)就是一维DP

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        sumnums = 0
        maxsum = nums[0]
        for num in nums:
            sumnums = sumnums + num
            maxsum = max(maxsum, sumnums)
            if sumnums < 0:
                sumnums = 0
        return maxsum

第二种方法：binary search

二刷：

这道题要求 求连续的数组值，加和最大。

试想一下，如果我们从头遍历这个数组。对于数组中的其中一个元素，它只有两个选择：

1. 要么加入之前的数组加和之中（跟别人一组）

2. 要么自己单立一个数组（自己单开一组）

   所以对于这个元素应该如何选择，就看他能对哪个组的贡献大。如果跟别人一组，能让总加和变大，还是跟别人一组好了；如果自己起个头一组，自己的值比之前加和的值还要大，那么还是自己单开一组好了。

所以利用一个sum数组，记录每一轮sum的最大值，sum[i]表示当前这个元素是跟之前数组加和一组还是自己单立一组好，然后维护一个全局最大值即位答案。

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        cursum = 0
        result = float('-inf')
        for num in nums:
            cursum = max(cursum+num, num)
            result = max(cursum, result)
        return result