Array & StringBeginner
Kadane's Algorithm
Track the maximum subarray sum ending at each position, resetting when the running sum becomes negative.
Problem: Maximum Subarray (Kadane's Algorithm)
Find the contiguous subarray in [-2, 1, -3, 4, -1, 2, 1, -5, 4] with the largest sum.
-2
1
-3
4
-1
2
1
-5
4
i
Initialize with arr[0] = -2
Start with currentSum = maxSum = -2. This is our baseline.
Current Sum: -2Max Sum: -2
Step 1/9
Speed:
When to Use
- Maximum subarray sum
- Maximum product subarray
- Circular subarray problems
Key Indicators
- Maximum/minimum subarray
- Contiguous elements
- Running sum/product
Complexity
Time
O(n)
Space
O(1)
Common Problems
Maximum SubarrayMaximum Product SubarrayMaximum Circular Subarray Sum
Code
maxSum = currentSum = arr[0]
for i in range(1, n):
currentSum = max(arr[i], currentSum + arr[i])
maxSum = max(maxSum, currentSum)Want all 29 patterns with detailed visual walkthroughs?
The complete book includes 84 practice problems, full decision tree, and illustrated step-by-step solutions.
Book Coming Soon ($4.99)