Medium
Dynamic Programming
Maximum Subarray
Extend the running sum, or restart at the current element — whichever is larger.
Approach
Kadane's algorithm keeps the best subarray sum ending at the current index: current = max(num, current + num). Track the overall maximum as you go. Restarting whenever the running sum would drag you down is the whole trick.
Time complexity
O(n)
Space complexity
O(1)
Common mistake
Initializing the max to 0 — with all-negative inputs the answer is the least-negative element, not 0.
See it run, step by step
Generate an interactive lesson for Maximum Subarray — trace every variable and watch the algorithm execute until it clicks.
Start a lesson on Maximum Subarray