Explain Kadane's Algorithm (Maximum Subarray Sum). What is its complexity?

Difficulty: 6/10

Maximum Subarray, Dynamic Programming, Time Complexity

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.

Scenario Questions

0-2 years experience

1Given an integer array of length eight, how would you find the maximum sum of a contiguous subarray using O(n) time?
2If the input array is [-2, 1, -3, 4, -1, 2, 1, -5, 4], walk me through the steps of your algorithm and the final result.
3What would your solution return for an array that contains only negative numbers, and why?

Follow-up Questions

What does your algorithm return when every number in the array is negative?
How would you modify the solution to also return the start and end indices of the optimal subarray?
Can you discuss the space complexity and whether it can be reduced further?