Purpose
To find a non-empty subarray with the largest sum in O(n) time, note that for an array of all negatives, we will just return a sub-array of size 1 of the largest number in that array.
Note that a sub-array must be contiguous.
This algorithm is used to solve Leetcode - Best Time to Buy and Sell Stock with applications in 2-pointer and sliding window situations.
How it works
- Keep track of a maxSum, and currSum
- Iterate throughout the array
- Check to make sure currSum is not negative, if it is, reset it to 0
- Add the current number to currSum
- Set maxSum to the max(maxSum, currSum)
- Return maxSum
You can modify Kadane’s algorithm to use a sliding window approach which returns the indices of the sub-array instead of its sum…
How it works
- The same idea…
- Keep track of the maxSum, currSum, but now also maxL, and maxR which are your result L and R pointers
- Iterate through the array
- if currSum < 0, reset it to 0 and set L = R
- if currSum > maxSum, set maxSum = currSum, and set maxL and maxR