How do you solve Maximum Subarray?

Arrays & Strings/Practice/Maximum Subarray

Maximum Subarray (Kadane) - Visual Walkthrough

mediumTime: O(n)Space: O(1)

Sweep the array while keeping two numbers: the best sum of a subarray ending here, and the best sum seen anywhere. At each element, either extend the current run or throw it away and start fresh - whichever is bigger.

Why it works

Any subarray with a negative running prefix can only hurt what comes after it, so the optimal answer never keeps a losing prefix. Dropping it the moment it goes negative is what makes one pass with two variables enough: O(n) time, O(1) space.

The problem

Given an integer array nums, find the contiguous subarray (containing at least one element) which has the largest sum and return its sum.

Hints

Track the current running sum and the global maximum.
If adding the next element makes the sum smaller than starting fresh, reset.
current = max(nums[i], current + nums[i])

Test cases

Input	Expected
`max_subarray([-2,1,-3,4,-1,2,1,-5,4])`	`6`
`max_subarray([1])`	`1`
`max_subarray([5,4,-1,7,8])`	`23`

Reference starter code

def max_subarray(nums):
    # Implement Kadane's algorithm
    pass

print(max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))  # 6
print(max_subarray([1]))                                  # 1
print(max_subarray([5, 4, -1, 7, 8]))                     # 23

Try it yourself

Solve it in the browser editor with real test cases and instant feedback - free, no signup needed.

Try it yourself Learn the concept first

Next challenge in this topic: Minimum Window Substring

Studying Arrays & Strings but not ready to grind? Get the 30-day plan by email.

One email with the study plan. No spam, unsubscribe anytime.