Kadane's Algorithm Visualization
Find the contiguous subarray with the largest sum in O(n) time.
Ready to start
Ready
Speed
Pseudocode
1function maxSubArray(arr)
2 currentSum = arr[0]
3 maxSum = arr[0]
4
5 for i = 1 to n-1
6 if arr[i] > currentSum + arr[i]
7 currentSum = arr[i]
8 else
9 currentSum += arr[i]
10
11 if currentSum > maxSum
12 maxSum = currentSum
13
14 return maxSum
Time Complexity
All CasesO(n)
Key Insight:
If the current subarray sum becomes negative, it's better to restart from the next element than to carry the negative burden forward.