← Back to Home
Kadane's Algorithm
An efficient algorithm to find the contiguous subarray within a one-dimensional array of numbers that has the largest sum.
Visualization
Step 1 / 11
Speed:
Details
Analogy
Think of analyzing a stock's daily price changes to find the most profitable period. You track the profit of your current 'trade.' If the profit drops below zero, you 'sell' and start a new trade the next day, since holding on would only hurt your gains. You always remember the single most profitable trade you've seen.
Purpose
To solve the maximum subarray problem in linear time.
Use Cases
Used in data analysis, financial analysis (e.g., finding periods of maximum profit from stock prices), and computer vision (e.g., image processing).
Algorithm Steps
Line 1
1
maxSoFar = -infinity
2
maxEndingHere = 0
3
for each element x in arr:
4
maxEndingHere = maxEndingHere + x
5
if maxSoFar < maxEndingHere:
6
maxSoFar = maxEndingHere
7
if maxEndingHere < 0:
8
maxEndingHere = 0
9
return maxSoFar
Current
Executed
Pending
Explanation
What's Happening?
Step 1/11
Start. Max so far = -∞, Current max = 0.
Updates with each step • Clickfor full view
Code Implementation
def max_sub_array_sum(arr):
max_so_far = -float('inf')
max_ending_here = 0
for x in arr:
max_ending_here = max_ending_here + x
if max_so_far < max_ending_here:
max_so_far = max_ending_here
if max_ending_here < 0:
max_ending_here = 0
return max_so_far