Questions
13 of 19
Explain Kadane's Algorithm (Maximum Subarray Sum). What is its complexity?
Difficulty: 4/10
Kadane's Algorithm
Kadane's Algorithm finds the maximum sum of a contiguous subarray in a single pass. At each position, we decide whether it is better to extend the current subarray or start a new subarray at the current element.
javascript
- 1
Time complexity: O(n).
- 2
Auxiliary space: O(1).
- 3
The algorithm works with negative values when initialized correctly.
- 4
The decision is based on whether extending the previous subarray improves the current sum.
- 5
The algorithm can be extended to track the actual start and end indexes of the best subarray.
Follow-up Questions
- How would you return the actual maximum subarray?
- How would you handle an empty array?
- Can Kadane's Algorithm be adapted for circular arrays?