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.

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.

Solution: DP

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

Solution: Divide & Conquer

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """

        def max_sub(low, high):
            if low >= high:
                return nums[high]
            mid = low + (high - low) / 2
            left = max_sub(low, mid)
            right = max_sub(mid + 1, high)
            crossing = max_crossing_sub(low, mid, high)
            return max(left, right, crossing)

        def max_crossing_sub(low, mid, high):
            sum = 0
            max_left = float('-inf')
            for idx in xrange(mid, low - 1, -1):
                sum += nums[idx]
                max_left = max(max_left, sum)
            sum = 0
            max_right = float('-inf')
            for idx in xrange(mid + 1, high + 1):
                sum += nums[idx]
                max_right = max(max_right, sum)
            return max_left + max_right

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

Lessons:

• The divide-and-conquer algorithm was described in Introduction to Algorithms (p68).