Maximum Subarray

PracticeNeetCode ↗LeetCode ↗

Given an integer array nums, find the contiguous subarray (with at least one number) that has the largest sum, and return that sum.

Example

Key Pointers

• This is Kadane's algorithm: a running sum that drops below the value of the current element alone is worse than restarting from that element.
• Track two values while scanning: the best sum ending exactly at the current index, and the best sum seen anywhere so far.
• A subarray can't be empty — if every number is negative, the answer is still the least negative single element.

Step-by-Step Analysis

1. Initialize curSum and maxSum both to nums[0].
2. For each subsequent number n: curSum = max(n, curSum + n) — either extend the running subarray or start fresh at n.
3. Update maxSum = max(maxSum, curSum) after each step.
4. Return maxSum once the array is exhausted.

Complexity

Time: O(n) — Space: O(1)

Code

def maxSubArray(nums: list[int]) -> int:
    curSum = maxSum = nums[0]
    for n in nums[1:]:
        curSum = max(n, curSum + n)
        maxSum = max(maxSum, curSum)
    return maxSum

Code Explanation

How the solution above works, piece by piece.

1. curSum = the best sum of a subarray that ends exactly at the current element.
2. curSum = max(n, curSum + n): either extend the previous subarray or start fresh at n. Starting fresh wins exactly when the running sum has gone negative, since a negative prefix only drags the total down.
3. maxSum keeps the best curSum seen anywhere.
4. Starting from nums[0] (not 0) makes an all-negative array return its largest element.
5. This is Kadane's algorithm: one pass, O(n) time, O(1) space.

Visual Walkthrough

Running it on nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]:

Video Explanation

NeetCode — Amazon Interview Question, LeetCode 53