53. Maximum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Example 2:

Input: nums = [1]
Output: 1

Example 3:

Input: nums = [0]
Output: 0

Example 4:

Input: nums = [-1]
Output: -1

Example 5:

Input: nums = [-2147483647]
Output: -2147483647

Constraints:

1 <= nums.length <= 2 * 10⁴
-2³¹ <= nums[i] <= 2³¹ - 1

Source

Code

In [1]:

def max_subarray(nums):
    """Dynamic Programming solution
    Time Complexity O(n)
    Space complexity O(n)
    """
    dp = [0]*len(nums)
    max_sum = dp[0] = nums[0]
    for i in range(1, len(nums)):
        dp[i] = max(dp[i-1]+nums[i], nums[i])
        if dp[i] > max_sum:
            max_sum = dp[i]
    return max_sum

In [2]:

def max_subarray(nums):
    """Kadane's Algorithm.
    Time Complexity O(n)
    Space complexity O(1)
    """
    if not nums:
        return None
    curr_sum = max_sum = nums[0]
    for number in nums[1:]:
        curr_sum = max(number, curr_sum + number)
        max_sum = max(max_sum, curr_sum)
    return max_sum

In [3]:

def max_subarray(nums):
    """Variation of Kadane's Algorithm (bit faster).
    Time Complexity O(n)
    Space complexity O(1)
    """
    max_sum = None
    curr_sum = 0
    for number in nums:
        curr_sum += number
        if max_sum is None or max_sum < curr_sum:
            max_sum = curr_sum
        if curr_sum < 0:
            curr_sum = 0
    return max_sum

Check

In [4]:

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
max_subarray(nums)

Out[4]:

In [5]:

nums = [-2147483647]
max_subarray(nums)

Out[5]:

-2147483647

In [6]:

nums = [8, -19, 5, -4, 20]
max_subarray(nums)

Out[6]:

In [7]:

nums = [-2, -1]
max_subarray(nums)

Out[7]:

-1

In [8]:

nums = [-1,1,2,1]
max_subarray(nums)

Out[8]:

In [9]:

nums = [1]
max_subarray(nums)

Out[9]:

In [10]:

nums = [0]
max_subarray(nums)

Out[10]:

In [11]:

nums = [-1]
max_subarray(nums)

Out[11]:

-1

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.

Code

In [12]:

def max_subarray(nums):
    """divide and conquer approach.
    Time Complexity T(n) = O(nlogn)
    Space Complexity logn?
    +info: https://www.youtube.com/watch?v=yBCzO0FpsVc
    """
    def divide(nums, start, end):
        """divide function"""
        if (start == end):   # Base Case: Only one element
            return nums[start]
        middle = (start + end) // 2
        return max(divide(nums, start, middle),
                   divide(nums, middle+1, end),
                   merge(nums, start, middle, end))

    def merge(nums, start, middle, end):
        """merge (conquer) function"""
        curr_sum = 0
        left_sum = -float("inf")
        for i in range(middle, start-1, -1):  # expand from the middle toward left
            curr_sum = curr_sum + nums[i]
            if (curr_sum > left_sum):
                left_sum = curr_sum  # and keep track of max sum

        curr_sum = 0  # reset and proceed to the right
        right_sum = -float("inf")
        for i in range(middle + 1, end + 1):  # expand from the middle toward right
            curr_sum = curr_sum + nums[i]
            if (curr_sum > right_sum):
                right_sum = curr_sum  # and keep track of max sum
       
        return max(left_sum + right_sum, left_sum, right_sum)
        # returning only left_sum + right_sum will fail for [-2, 1]


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

Check

In [13]:

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
max_subarray(nums)

Out[13]:

In [14]:

nums = [-2147483647]
max_subarray(nums)

Out[14]:

-2147483647

In [15]:

nums = [8, -19, 5, -4, 20]
max_subarray(nums)

Out[15]:

In [16]:

nums = [-2, -1]
max_subarray(nums)

Out[16]:

-1

In [17]:

nums = [-1,1,2,1]
max_subarray(nums)

Out[17]:

In [18]:

nums = [1]
max_subarray(nums)

Out[18]:

In [19]:

nums = [0]
max_subarray(nums)

Out[19]:

In [20]:

nums = [-1]
max_subarray(nums)

Out[20]:

-1