Maximum Subarray (Kadane)

Med
Code
Loading editor...
Tap Analyze to see visualization
Variables

Run code to see variables

Output

Console output will appear here

Press Space to start•← → to step•? all shortcuts

Solution Guide: Maximum Subarray (Kadane)

Approach

Use Kadane's algorithm: at each position, decide whether to extend the current subarray or start a new one. If the running sum plus the current element exceeds the element alone, extend. Otherwise, start fresh. Track the global maximum sum throughout.

Complexity Analysis

Time
O(n)
Space
O(1)

Pattern

Kadane's Algorithm

Why It Works

A negative running sum can only hurt future sums. Resetting when currentSum + nums[i] < nums[i] ensures we never carry forward a net-negative prefix, and the global max captures the best subarray seen.

Updated Feb 2026