leetcode 53. 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.

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

class Solution:
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        negative_sum = this_sum = max_sum = 0
        all_negative = True
        for i in range(len(nums)):
            this_sum += nums[i]
            
            if this_sum >= max_sum: # 考虑[-1, 0]的情况，所以条件是大于等于
                all_negative = False # nums不是全部负数
                max_sum = this_sum
            elif this_sum < 0:
                if negative_sum == 0: # 第一次发现负数
                    negative_sum = this_sum
                elif negative_sum < this_sum:
                    negative_sum = this_sum
                this_sum = 0
                
        return negative_sum if all_negative else max_sum

思路：
这种方法属于比较tricky的一种，时间复杂度是O(n)，空间复杂度是O(1)。

this_sum 每次累加成负数时，都会重置为0，然后又开始累加，等于隐式的将sums分段，每段都能得出一个max_sum，然后这些max_sum中最大的就是我们想要的。

这里要考虑nums全是负数的情况，我们用一个all_negative来当成flag，如果全是负数，就返回negative_sum。

negative_sum 就是每个隐式分段中最大的负数sum。

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

思路：
这种方法就比较简洁了，算是动态规划的一个简单示例。
如果我们知道在 i 这个位置的max subarray（定为 B_i），那么在 i+1 位置的max subarray是什么呢（B_i+1是什么）？

显然，这个max subarray要么包含 i 位置的max subarray，要么不包含。
即：B_i+1 = max(A_i+1, A_i+1+B_i)，其中 A_i+1 为在 i+1 位置的元素。

时间复杂度为O(n)，空间复杂度为O(1)。详细解释：Kadane's algorithm