53. Maximum Subarray

[huimeich]

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.

[huimeich]

def maxSubArray(self, nums: List[int]) -> int:
    def helper(left: int, right: int) -> int:
        def cross_helper(left: int,mid: int, right: int) -> int:
            if left == right:
                return nums[left]
            left_sum = float('-inf')
            summ = 0
            for i in reversed(range(left, mid + 1)):
                summ += nums[i]
                left_sum = max(summ, left_sum)
            right_sum = float('-inf')
            summ = 0
            for i in range(mid+1, right+1):
                summ += nums[i]
                right_sum = max(summ, right_sum)
            return left_sum + right_sum

        if left == right:
            return nums[left]
        mid = left + (right - left) // 2
        left_max = helper(left, mid)
        right_max = helper(mid + 1, right)
        cross_max = cross_helper(left, mid, right)
        return max(left_max, right_max, cross_max)

    return helper(0, len(nums) - 1)

[huimeich]

def maxSubArray(self, nums: List[int]) -> int:
    ans = float('-inf')
    summ = 0
    for num in nums:
        summ = max(num, summ + num)
        ans = max(summ, ans)
    return ans