roadmap/dynamic-programming/Maximum Subarray

Maximum Subarray

MediumAmazonGoogleMicrosoftApple

Problem

Given an integer array nums, find the subarray with the largest sum and return the sum.

Intuition — the key insight

Kadane's algorithm: at each position, decide whether to extend the previous subarray or start fresh. If the running sum becomes negative, it only hurts future elements — reset to 0.

Approach

Kadane's algorithm

curr = 0, best = nums[0]. For each num: curr = max(num, curr+num). best = max(best, curr). Return best.

Complexity

Time

O(n)

Space

O(1)

Single pass, two variables.

Solution code

Python

def maxSubArray(self, nums: List[int]) -> int:
    curr = best = nums[0]
    for num in nums[1:]:
        curr = max(num, curr + num)
        best = max(best, curr)
    return best

Edge cases to remember

⚠All negative: return the least negative (largest single element)

⚠Single element: return it directly