Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
[3, 5, -9, 1, 3, -2, 3, 4]
9
This is a very famous algorithm and a really clever use of dynamic programming.
There are two core parts to this, keeping track of a local accumulating maximum and a global maximum.
The local maximum is the maximum of two values; the running local maximum including the current number or simply the current number.
The former of those two values is very interesting because it takes care of negative values for us, for example when the algorithm is on index 3 of the input array; it can choose between the running local maximum of -1 and itself 1, or simply 1. The latter is a greater value and will be chosen.
At that point in the algorithm, the global maximum would still be at 8 and can't be overriden as the current local running max is 1. This is very interesting because if index 3 is the last item of the array; then you have the correct answer.
However, if index 4 were the number 10; then the local running max plus 10 would beat the running global max of 8.
Another important note: if the previous number was a negative 2 and the current number is 3 and the local running max is 1, then that negative 2 is included as part of the potential maximum subarray range. It's really all about a negative a negative number really is, if the negative number(s) ultimately make the range too negative; then the first positive number met will fix that.
The algorithm essentially lets every positive number have the chance to start working towards accumulating a global max that is greater than the current global max.
The above means that going from negative to positive; only the positive is recognized. And going from a greater number to less one, the global maximum is still respected and the local running maximum is accumulated.
Space: O(1)
The only additional variables created are primitive types.
Time: O(n)
The input array is only iterated over once and only constant time and space operations are performed for each iteration.
function maximumSubArray(nums) {
let currSum = nums[0]
let maxSum = nums[0]
for(let i = 1; i < nums.length; i++) {
currSum = Math.max(currSum + nums[i], nums[i])
maxSum = Math.max(maxSum, currSum)
}
return maxSum
};