30% off Lifetime Premium Access expires December 2nd!

30% off Lifetime Premium Access expires Dec 2nd!

Your Dashboard

Interview Coaching

Mock Interviews

1:1 Mentorship

Salary Negotiation

Practice

Learn

System Design

ML System Design

Code

Behavioral

Salary Negotiation

Interview Guides

Blog

Community

Interview Questions

Interview Experiences

Peer System Design Library

Ask The Community

Discord

Refer a Friend

Pricing

Become a Coach

⌘K

Pricing Become a Coach

⌘K

Get Premium

Leetcode 53. Maximum Subarray

Find the contiguous subarray within an integer array that yields the maximum possible sum and return that sum. This is typically solved in O(n) with Kadane's algorithm (with an alternative divide-and-conquer approach as a follow-up).

Asked at:

DESCRIPTION

Find the contiguous subarray within an integer array that yields the maximum possible sum and return that sum.

Input:


nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

Output:

Explanation: The subarray [4, -1, 2, 1] has the largest sum of 6

Constraints:

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
Must return the sum of the maximum subarray
The subarray must contain at least one element

Understanding the Problem

Let's understand what we're being asked to do. We have an array like [-2, 1, -3, 4, -1, 2, 1, -5, 4] and need to find the contiguous subarray (elements that are next to each other) with the largest sum.

Tracing through: the subarray [4, -1, 2, 1] has sum 6, which is the maximum possible. Note that we can't skip elements - [4, 2, 1] wouldn't be valid because it's not contiguous.

Important constraint: We must pick at least one element (the subarray can't be empty).

Edge cases to consider: What if all numbers are negative? (pick the least negative one). What if the array has only one element? What if the entire array gives the maximum sum?

Brute Force Approach

The brute force approach checks every possible contiguous subarray by using nested loops. The outer loop picks the starting index, the inner loop picks the ending index, and for each pair we calculate the sum of elements in that range. We track the maximum sum seen across all possible subarrays. This approach is straightforward but inefficient because it recalculates sums from scratch for overlapping subarrays.

def max_subarray_sum(nums):
    """
    Find the contiguous subarray with maximum sum using brute force.
    Check every possible subarray by trying all start and end positions.
    """
    if not nums:
        return 0
    
    max_sum = float('-inf')
    n = len(nums)
    
    # Outer loop: pick starting index
    for start in range(n):
        # Inner loop: pick ending index
        for end in range(start, n):
            # Calculate sum of subarray from start to end
            current_sum = 0
            for k in range(start, end + 1):
                current_sum += nums[k]
            
            # Update maximum sum if current is larger
            if current_sum > max_sum:
                max_sum = current_sum
    
    return max_sum

Start brute force maximum subarray algorithm

0 / 686

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n²) We have nested loops iterating through all possible start and end positions, and for each pair we sum the elements, leading to quadratic time complexity

Space Complexity: O(1) We only use a few variables to track the current sum and maximum sum, regardless of input size

Building Intuition

At each position, we face a decision: should we extend the current subarray by including this element, or start a fresh subarray from this element?

If the sum we've built so far is negative, it will only drag down future elements - we're better off starting fresh!

By making this local decision at each step (extend vs. restart), we can find the global maximum in a single pass through the array.

This transforms what seems like a problem requiring checking all possible subarrays O(n²) into a linear O(n) solution by recognizing that negative accumulated sums are never worth keeping.

Imagine you're climbing a mountain range, tracking your altitude. At each step, you can either continue from your current altitude or reset to ground level.

If your current altitude is below ground (negative sum), you'd reset to ground level before continuing. You keep track of the highest point you've reached overall. This 'running sum with reset' pattern naturally finds the best contiguous segment.

Common Mistakes

Forgetting to handle the all-negative case - the algorithm naturally handles this by picking the least negative element

Initializing the maximum sum to 0 instead of the first element or negative infinity - this fails when all numbers are negative

Confusing subarray (contiguous) with subsequence (can skip elements) - this problem requires contiguous elements

Not resetting the running sum when it becomes negative - this is the core insight of Kadane's algorithm

Trying to track the actual subarray indices while learning the algorithm - focus on understanding the sum calculation first, then add index tracking as an extension

Optimal Solution

Kadane's algorithm solves this in one pass by maintaining a running sum of the current subarray. At each element, we decide whether to extend the current subarray (add the element to our running sum) or start a new subarray from this element (if the running sum has become negative). We track the maximum sum seen so far across all positions. This greedy approach works because a negative running sum can never help maximize future subarrays, so we reset whenever it goes negative.

def max_subarray_sum(nums):
    """
    Find the contiguous subarray with the maximum sum using Kadane's algorithm.
    Time: O(n), Space: O(1)
    """
    # Initialize max_sum with first element (handles all-negative arrays)
    max_sum = nums[0]
    # Current running sum of subarray ending at current position
    current_sum = nums[0]
    
    # Iterate through array starting from second element
    for i in range(1, len(nums)):
        # Key decision: extend current subarray or start new one
        # If current_sum is negative, it can't help future sums, so reset
        current_sum = max(nums[i], current_sum + nums[i])
        
        # Update global maximum if current subarray sum is better
        max_sum = max(max_sum, current_sum)
    
    return max_sum

Start Kadane's algorithm to find maximum subarray sum

0 / 34

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n) We make a single pass through the array, making a constant-time decision at each element

Space Complexity: O(1) We only need two variables: one to track the current subarray sum and one to track the global maximum

What We've Learned

Kadane's algorithm pattern: When you need to find an optimal contiguous subarray (maximum/minimum sum, product), think Kadane's algorithm - it works by making a local decision at each element (extend current subarray vs. start fresh) that leads to a global optimum, avoiding the O(n²) brute force of checking all subarrays.
Local vs. global maximum tracking: Maintain two variables: current_sum (best subarray ending at current position) and max_sum (best seen so far). At each element, decide: `current_sum = max(nums[i], current_sum + nums[i])` - this captures whether adding the current element improves the running sum or if starting fresh is better.
Greedy subarray extension principle: The key insight is that if your running sum becomes negative, it can never help future elements - discard it and restart. A negative prefix will only drag down any positive suffix, so the greedy choice to abandon it is always optimal.
All-negative array edge case: A common mistake is initializing `max_sum = 0`, which fails when all numbers are negative (would return 0 instead of the least negative number). Always initialize `max_sum = nums[0]` or `float('-inf')` to handle arrays with only negative values correctly.
O(n) time with O(1) space optimization: Unlike dynamic programming solutions that store results for each position in an array, Kadane's only needs the previous state to compute the next, achieving constant space complexity - this is a key pattern for optimizing DP solutions when you only reference the immediate previous result.
Stock trading and time-series analysis: This pattern extends beyond coding interviews to financial analysis (maximum profit periods), signal processing (detecting strongest signal intervals), and resource allocation (identifying peak demand windows) - any domain where you need to find optimal consecutive time periods in sequential data.

Test Your Understanding

Why is array the right data structure for this problem?

array provides the optimal access pattern

It's the only data structure that works

It's the easiest to implement

It uses the least memory

Select an answer to see the explanation

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Early November, 2025

Microsoft

Mid-level

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

Mid September, 2025

Senior

Extend it to support streaming mode inputs

Late July, 2025

Uber

Mid-level

same as leetcode

Get Premium to View All 8 Reports

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More

Leetcode 53. Maximum Subarray

DESCRIPTION

Understanding the Problem

Brute Force Approach

Test Your Knowledge

Complexity Analysis

Building Intuition

Common Mistakes

Optimal Solution

Test Your Knowledge

Complexity Analysis

What We've Learned

Related Concepts and Problems to Practice

Test Your Understanding

Question Timeline

Comments

Questions

Learn

Links

Legal

Contact