Mathwizurd.com is created by David Witten, a mathematics and computer science student at Vanderbilt University. For more information, see the "About" page.

Maximum Subarray

Problem

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.

Thought Process

Immediately, you should come up with a brute force solution, just so you have a solution that works. Here is the brute force solution: check every subset, and take the maximum of that. Think about what that would entail. You would have to take all n subsets of length 1, n-1 subsets of length 2. There are n(n+1)/2 subsets, or O(n^2) time.

We now have an upper bound to solve this problem. Let’s figure out our goal. It’s either O(n), or O(n log n). O(n log n) happens when sorting occurs. There should be no sorting here.

Goal: O(n)

The maximum subarray equals the maximum of the greatest subarray ending at each point.

Let’s go through the array [-2,1,-3,4,-1,2,1,-5,4]

The greatest subarray ending with array[0], or -2 is -2.
The greatest subarray ending with 1 is either (-2 + 1) or 1, meaning it’s 1.
The greatest subarray ending in -3 is either -3 or (1 + -3).
… We keep doing this and we get the array

[-2,1,-2,4,3,5,6,1,5]. The largest value is 6.

Optimize space

Note that we only needed to save two variables, the maximum ending at that point and the maximum overall. Therefore, we don’t even need to save that entire list.

Solution

def maxSubArray(nums):
    current = best = nums[0]
    for i in nums[1:]:
        current = max(current + i, i)#Best subset ending at that point
        best = max(best, current)#Best subset overall
    return best




Find the H-Index