Kadane's Algorithm
Visualize finding the Maximum Subarray Sum in O(n) time.
Current Sum
0
Max Sum
-
Ready to find Max Subarray Sum.
-2
01
1-3
24
3-1
42
51
6-5
74
8Intuition
If the current subarray sum becomes negative, it's better to discard it and start a new subarray from the next element. A negative prefix will only reduce the sum of any future subarray.
Concept
- Idea: Iterate through the array, adding elements to
currentSum. - Update Max: If
currentSum > maxSum, updatemaxSum. - Reset: If
currentSum < 0, resetcurrentSumto 0 (start fresh).
How it Works
Algorithm:
- Initialize
currentSum = 0,maxSum = -Infinity. - For each element
xin array: currentSum += xmaxSum = max(maxSum, currentSum)- If
currentSum < 0, setcurrentSum = 0.
Step-by-Step Breakdown
Watch the visualization:
- Blue box shows the current growing subarray.
- Green line at bottom shows the best subarray found so far.
- Notice how the blue box resets when the sum turns negative.
When to Use
- Finding the maximum sum contiguous subarray.
- Stock trading problems (max profit).
When NOT to Use
- If all numbers are negative (requires a small modification to return the max single element).
How to Identify
"Maximum subarray sum", "Largest sum contiguous segment".
Frequently Asked Questions
What is Kadane's Algorithm?
Visualize finding the Maximum Subarray Sum in O(n) time.
What is the time complexity of Kadane's Algorithm?
The time complexity is: Best case varies, Average case O(N), Worst case varies. Space complexity is varies.