To find the subarray with the maximum sum, we use a modified version of Kadane's Algorithm, which not only calculates the maximum sum but also keeps track of the subarray boundaries (start and end indices).
Understanding the Problem
The array may contain positive numbers, negative numbers, or even all negatives. We are interested in the subarray (a contiguous part of the array) whose sum is the highest among all possible subarrays.
Different Scenarios
- All Positive Elements: The whole array is the maximum subarray since every additional number only increases the sum.
- All Negative Elements: We cannot pick multiple elements here. The maximum subarray is simply the single element with the least negative value (i.e., closest to zero).
- Mixed Elements: This is where the real use of Kadane's algorithm shines. As we traverse, we build up the current sum, but if adding the current element makes the sum worse than just starting from the current element, we reset the current sum. While doing this, we track the subarray bounds whenever a new maximum is found.
- Empty Array: If the array is empty, there is no subarray. We can return 0 as the maximum sum and an empty list for the subarray.
- Zeros in Array: In cases where all values are zero, the result should be [0] with a sum of 0 — usually picking the first one.
This method works efficiently in linear time O(n) and gives us not just the value, but also the actual subarray that yields this maximum sum.
By carefully handling resets and updates of subarray bounds, we ensure that the printed subarray reflects the earliest occurrence of the maximum sum.