53. Maximum Subarray

https://leetcode.com/problems/maximum-subarray/description/

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.

Solution1: (Dynamic Programming)

$\text{MaxSum}=\{A[i],\ r_{i-1}+A[i]\}$

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

Solution2:

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        self.nums = nums
        return self.findmax(0, len(nums)-1)
    
    def findmax(self, start, end):
        if start == end:
            return self.nums[start]
        mid = (start + end)/2
        maxleft = self.findmax(start, mid)
        maxright = self.findmax(mid+1, end)
        maxmid = self.nums[mid]
        current = self.nums[mid]
        for i in range(mid-1, start-1, -1):
            current += self.nums[i]
            if current > maxmid:
                maxmid = current
        current = maxmid
        for i in range(mid+1, end+1, 1):
            current += self.nums[i]
            if current > maxmid:
                maxmid = current
        return max(maxleft, maxmid, maxright)