Kadane's algorithm can find us the maximum contiguous subarray sum and the starting and ending index but the contiguous subarray is not necessarily smallest always. For example : 10 5 -12 7 -10 20 30 -10 50 60. Cumulative sum of the whole array is 150. Cumulative sum of the last 5 elements is also 150. How would you modify the algorithm to find the smallest subarray?
1 Answers
0
votes
We can solve this in O(n) with two traversals. In the first traversal, use Kadane's algorithm to find the maximum sum, S. For the second traversal, there is a good description at https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/solution/ of maintaining a two-ended queue of indexes to the array's prefix sums so as to be able to keep the indexes of a monotonically increasing list of prefix_left that we can compare with prefix_right (the current index) subtracted by S. We are looking for the smallest r - l such that prefixes[l] ≤ prefixes[r] - S. While prefixes[l] ≥ prefixes[r], pop left. Then while prefixes[l] ≤ prefixes[r] - S update the solution and pop left (since any greater r index would only generate a larger interval against the same l). Append y to the queue.
