Finds the contiguous subarray with the largest sum in a single pass. Works with negative numbers by restarting the running window whenever it would only drag the total down.
Finds the contiguous subarray with the largest sum in a single pass. Works with negative numbers by restarting the running window whenever it would only drag the total down.
Time complexity: O(n). Space complexity: O(1).
Core idea — Sweep left to right keeping the best sum of a subarray that ends at the current element; whenever that running sum turns negative, start a fresh window here.
What each pass accomplishes — At each index you decide to either extend the current window or restart it, then compare against the best total seen so far. After visiting index i you know the maximum subarray sum within the first i+1 elements — so one full pass settles the whole array.
Use the interactive visualizer above to run Kadane's Algorithm (Maximum Subarray) on your own input and watch every comparison, swap, and operation animate step by step — pause, scrub, or replay at any speed.