Algorithms and Data Structures · Middle · Question 47 of 75
What is the idea of Kadane's algorithm for the maximum subarray sum?
- 1Sort the array and add up all positive numbers
- ✓Correct answer: Track the best sum ending here: extend it or start over
- 3Check the sum of every possible subarray once
Explanation
cur = Math.max(x, cur + x), best = Math.max(best, cur). A negative running sum only hurts, so it's dropped. One pass, O(n), instead of O(n²) for all subarrays.