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