Kadane's Algorithm Visualization & Animation

Finds the maximum sum contiguous subarray in O(n) by deciding at each step whether to extend or restart.

## What is it? Kadane's Algorithm finds the maximum sum contiguous subarray of a given array in O(n) time. It handles arrays with negative numbers by deciding at each step whether to extend the current subarray or start fresh. ## How it works - Initialize `maxSum = arr[0]`, `currentSum = arr[0]` - For each element from index 1: - `currentSum = max(arr[i], currentSum + arr[i])` - If `currentSum + arr[i] < arr[i]`, starting fresh at `arr[i]` is better - `maxSum = max(maxSum, currentSum)` - Return `maxSum` ## When to use - Maximum subarray sum (LeetCode 53) - As a building block for Maximum Product Subarray, Circular Max Subarray - Any problem involving "best contiguous segment" ## Key Points - O(n) time, O(1) space — optimal - Works correctly when all elements are negative (returns the largest single element) - The decision at each step: "is the current element alone better than extending the previous subarray?"

Category: data-structure

Difficulty: intermediate

Time Complexity: O(n)

Space Complexity: O(1)

Kadane's Algorithm

intermediate

Finds the maximum sum contiguous subarray in O(n) by deciding at each step whether to extend or restart.

GFGLeetCode
Current Sum0
Max Sum0
Original Array
-2
[0]
1
[1]
-3
[2]
4
[3]
-1
[4]
2
[5]
1
[6]
-5
[7]
4
[8]

Extend window or start fresh?

Extend:0+-2=0
Restart:-2alone

Current element (examine)
Running window members
New maximum found