Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6.
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.
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, 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.
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.
def maxSubArray(nums): current = best = nums 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