The goal is to find the maximum sum of a contiguous subarray within a given array of integers. This is a classic problem and Kadane's Algorithm offers an elegant and efficient solution that works in O(n) time.
Understanding Different Cases
1. All Positive Numbers: If all elements are positive, the best strategy is to take the entire array. For example, in [1, 2, 3, 4], the answer is 10. There’s no need to exclude any elements.
2. All Negative Numbers: In cases where all numbers are negative, like [-3, -2, -1], you cannot get a positive sum. So the answer is simply the largest (least negative) number, which in this case is -1.
3. Mixed Positive and Negative: This is where Kadane's Algorithm shines. It keeps track of the current subarray sum and resets it to the current element if that element is better on its own. It also keeps updating the maximum sum seen so far. For example, in [-2, 1, -3, 4, -1, 2, 1, -5, 4], the subarray [4, -1, 2, 1] gives the maximum sum of 6.
4. Zeros or Zero as Maximum: In cases like [0, 0, 0] or [-2, -1, 0, -3], zero may be the largest value, and hence the maximum subarray sum is 0.
5. Single Element: For arrays like [5] or [-4], the result is the element itself because it's the only possible subarray.
6. Empty Array: If the array is empty, there are no elements to form a subarray, so by convention, the answer is 0
.
Why Kadane’s Algorithm is Efficient
Unlike brute-force methods that check every possible subarray (which takes O(n²) time), Kadane's Algorithm only makes one pass through the array. It dynamically decides whether to extend the current subarray or start a new one, making it highly efficient.
This approach works for all types of input arrays—positive, negative, mixed, or empty—and gives you the optimal solution every time.