MediumArrayDynamic ProgrammingDivide and ConquerUpdated Sep 2026

53. Maximum Subarray

Asked at Google, Meta, Amazon, Microsoft and 7 more

Difficulty

Medium

Time

O(n)

Space

O(1)

Pattern

Array

Companies

11

Problem

You are given an array of integers nums. Find one contiguous block of elements (a subarray) whose sum is as large as possible, and return that sum.

A subarray must be a run of neighbouring elements — you cannot skip elements or pick them from different places. The block must contain at least one element, so an empty subarray is not allowed.

The array may contain negative numbers, and it may be all negative. In that case the best block is the single largest element, because adding any other element would only make the sum smaller.

Pick one unbroken block

numssum = 6-21-34-121-54012345678These four neighbours add up to 6, the largest sum of any contiguous block.
The best block in this array is [4,-1,2,1], which sums to 6.

Constraints

  • ●1 <= nums.length <= 10^5
  • ●-10^4 <= nums[i] <= 10^4

Examples

Example 1
Inputnums = [-2,1,-3,4,-1,2,1,-5,4]
Output6
WhyThe block [4,-1,2,1] adds up to 4 - 1 + 2 + 1 = 6. Every other contiguous block sums to 6 or less.
Example 2
Inputnums = [1]
Output1
WhyThere is only one element, so the only possible subarray is [1] and its sum is 1.
Example 3
Inputnums = [5,4,-1,7,8]
Output23
WhyAll five elements together give 5 + 4 - 1 + 7 + 8 = 23. Dropping the -1 would break the block, so the whole array is the best choice.

Asked At

11 companies
CompanyDifficulty
GoogleMediumView all Google questions →
MetaMediumView all Meta questions →
AmazonMediumView all Amazon questions →
MicrosoftMediumView all Microsoft questions →
AppleMediumView all Apple questions →
NetflixMediumView all Netflix questions →
AdobeMediumView all Adobe questions →
AtlassianMediumView all Atlassian questions →
WalmartMediumView all Walmart questions →
BloombergMediumView all Bloomberg questions →
LinkedInMediumView all LinkedIn questions →

How to Think About It

1

At each position, you have two choices: extend the previous subarray or start fresh here. If the previous sum is negative, starting fresh is better.

2

The recurrence: maxEndingHere = max(nums[i], maxEndingHere + nums[i]). Either start a new subarray at nums[i] or extend the existing one.

3

Track the global maximum as you go. maxSoFar = max(maxSoFar, maxEndingHere). One pass through the array.

4

Why it works: maxEndingHere represents the best subarray ending at the current position. If the running sum goes negative, it's never worth extending — start fresh.

5

Edge cases: all negative numbers (return the largest single element), single element (return it).

Optimal Approach

Kadane's algorithm:
Step 1: Initialize maxEndingHere = nums[0], maxSoFar = nums[0].
Step 2: For each num in nums[1:]:
maxEndingHere = max(num, maxEndingHere + num)
maxSoFar = max(maxSoFar, maxEndingHere)
Step 3: Return maxSoFar.

The key insight: if maxEndingHere becomes negative, it's better to start fresh at the next element. A negative running sum can only hurt the next subarray.

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

Kadane's algorithm in one pass

nums-21-34-121-54012345678iStart: maxEndingHere = -2 and maxSoFar = -2, both taken from the firstelement.numsmaxEndingHere = 6-21-34-121-54012345678iAt index 6 the running sum reaches 6, and maxSoFar is updated to 6.maxEndingHere = max(num, maxEndingHere + num)maxSoFar = max(maxSoFar, maxEndingHere)if the running sum goes negative, start fresh
At each element we either extend the running block or start a new one, and we remember the best sum seen so far.
ComplexityTime O(n)Space O(1)One pass over the array, and only two running numbers are kept, so the cost is linear time and constant extra space.

What Trips People Up in Real Interviews

1

Confusing "maximum subarray" with "maximum element." The subarray must be contiguous, and you're looking for the maximum sum, not the maximum single element.

2

Not handling all-negative arrays. If all elements are negative, the answer is the largest (least negative) single element, not 0.

3

Trying to use a separate array for dp. Kadane's algorithm can be done in O(1) space with just two variables.

4

Forgetting to initialize the result. Set result = nums[0] (or negative infinity), not 0. If all elements are negative, 0 would be wrong.

5

Thinking the subarray must start at index 0. Kadane's allows the maximum subarray to start anywhere — it tracks the best ending at each position and the global best across all positions.

Solution Code

O(n) time
def maxSubArray(nums):
    max_ending_here = max_so_far = nums[0]
    for num in nums[1:]:
        max_ending_here = max(num, max_ending_here + num)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Maximum Subarray problem?

Given an integer array `nums`, find the subarray with the largest sum and return its sum. This is Kadane's algorithm, one of the most elegant DP solutions.

How do you solve Maximum Subarray?

The optimal approach runs in O(n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Maximum Subarray?

Maximum Subarray is asked at Google, Meta, Amazon, Microsoft, Apple, Netflix, Adobe, Atlassian, Walmart, Bloomberg, LinkedIn. It is a medium difficulty problem.

What are common mistakes on Maximum Subarray?
  • Confusing "maximum subarray" with "maximum element." The subarray must be contiguous, and you're looking for the maximum sum, not the maximum single element.
  • Not handling all-negative arrays. If all elements are negative, the answer is the largest (least negative) single element, not 0.
  • Trying to use a separate array for `dp`. Kadane's algorithm can be done in `O(1)` space with just two variables.
  • Forgetting to initialize the result. Set result = `nums[0]` (or negative infinity), not 0. If all elements are negative, 0 would be wrong.
  • Thinking the subarray must start at index 0. Kadane's allows the maximum subarray to start anywhere — it tracks the best ending at each position and the global best across all positions.