面试题 16.17. 连续数列

给定一个整数数组，找出总和最大的连续数列，并返回总和。

示例：

输入： [-2,1,-3,4,-1,2,1,-5,4]
输出： 6
解释： 连续子数组 [4,-1,2,1] 的和最大，为 6。

进阶：
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

Python 解答：
1.线性扫描

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        i = 0
        total = 0
        maxValue = nums[0]
        while i < len(nums):
            total += nums[i]
            if total > maxValue:
                maxValue = total
            if total < 0:
                total = 0
            i += 1
        return maxValue

2.分治

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        def helper(nums, l, r):
            if l < r:
                mid = (l+r) // 2
                left = helper(nums, l, mid)
                right = helper(nums, mid+1, r)
                i, j = mid, mid+1
                sum_left, sum_right = 0, 0
                max_1, max_2 = float('-inf'), float('-inf')
                while i >= l:
                    sum_left += nums[i]
                    if sum_left > max_1:
                        max_1 = sum_left
                    i -= 1
                while j <= r:
                    sum_right += nums[j]
                    if sum_right > max_2:
                        max_2 = sum_right
                    j += 1
                return max(left, right, max_1+max_2)
            else:
                return nums[l]
        return helper(nums, 0, len(nums)-1)