Maximum Subarray - Kadane's Algorithm

Array

Current Subarray

Current Index (i)

Current Sum

Maximum Sum

-∞

Max Subarray

Click "Step" or "Play" to start the visualization

Current Element

In Current Subarray

Max Subarray

Python Code - Kadane's Algorithm

                sum = 0
            
                max = -math.inf
            
                for i in range(len(nums)):
            
                    if sum == 0: start = i
            
                    sum += nums[i]
            
                    if sum > max:
            
                        max = sum
            
                        ans_start, ans_end = start, i
            
                    if sum < 0: sum = 0
            
                return max

Complexity Analysis

Time Complexity O(n) Space Complexity O(1)

Time Complexity: O(n)

Breakdown

Single pass through array of n elements
Each iteration: one addition, two comparisons
Update running sum and global maximum: O(1)
No nested loops or recursive calls

T(n) = n × O(1) = O(n)

Mathematical Intuition

Define maxEndingHere[i] as the maximum subarray sum ending at index i. The recurrence is: maxEndingHere[i] = max(nums[i], maxEndingHere[i-1] + nums[i]). This optimal substructure allows computing each entry in O(1) from the previous, yielding linear total time.

Key Insight

A negative running sum can never improve a future subarray—resetting to zero is always optimal, making this a valid greedy algorithm.

Space Complexity: O(1)

Breakdown

currentSum: running sum variable
maxSum: global maximum tracker
Optional: start/end indices for subarray bounds
No auxiliary arrays or recursion stack

S(n) = O(1) — fixed number of variables

Mathematical Intuition

The DP recurrence only depends on the immediately preceding value, not the entire history. This allows "space optimization" from O(n) tabulation down to O(1) by keeping only the previous state.

Key Insight

Kadane's algorithm is an online algorithm: it can process a stream of numbers without storing the entire input, outputting the current maximum at any point.