53. Maximum Subarray

Medium — Dynamic Programming, Divide and Conquer

Kadane's
Brute Force
Prefix Sum
Press "Play" or "Step" to walk through the algorithm.

Step

0 / 0

Operations

0

Best Sum

--

Best Range

[ , ]
Current index
In running window
Best subarray
Restart point
Algorithm Complexity (smaller bar = faster)
Brute Force
O(n²)
Time / Space: O(n²) / O(1)
Divide & Conquer
O(n log n)
Time / Space: O(n log n) / O(log n)
Kadane's
O(n)
Time / Space: O(n) / O(1)
Prefix Sum
O(n)
Time / Space: O(n) / O(1)