Maximum Subarray is one of the most celebrated algorithmic problems in the interview canon. It’s LeetCode #53, rated Medium, and it’s been a staple at Google, Amazon, Meta, Microsoft, and nearly every company that takes algorithms seriously. But its reputation extends well beyond LeetCode. The underlying algorithm, Kadane’s Algorithm, is a landmark result in computer science: a greedy technique that solves what initially feels like a dynamic programming problem in a single pass with constant space.

What makes this problem so instructive is the journey. The brute force is obvious, the O(n²) optimization is achievable, but the O(n) solution requires a genuine insight that many candidates can’t articulate even when they know the answer. Interviewers use this problem to distinguish candidates who understand why Kadane’s algorithm works, the greedy decision to reset the running sum when it turns negative, from those who’ve memorized the implementation without internalizing the reasoning.

This walkthrough builds the complete explanation from scratch: the brute force, the Kadane’s greedy insight, the DP framing that makes it rigorous, and the follow-up questions that interviewers use to probe depth.

---

The Problem

Given an integer array nums, find the subarray with the largest sum, and return that sum. A subarray is a contiguous portion of the array, not just any subset. (LeetCode #53)

Example

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

Output 6

The subarray [4,-1,2,1] has the largest sum of 6. The array contains both positive and negative numbers; the challenge is knowing when to extend the current subarray and when to start fresh. The subarray must be contiguous: you can’t skip the -1 and combine [4] and [2,1] separately.

Already comfortable with Kadane’s algorithm? Practice it in a mock interview →

---

What Interviewers Are Actually Testing

Maximum Subarray is a probe for greedy and DP thinking simultaneously. Interviewers watch whether you can derive the key decision rule, extend or reset, and whether you can frame the same algorithm as both a greedy technique and a DP recurrence.

Skill	What Interviewers Observe
Greedy decision reasoning	Do you articulate why a negative running sum should be discarded?
DP framing	Can you express the recurrence dp[i] = max(nums[i], dp[i-1] + nums[i])?
All-negative handling	Do you correctly initialize max_sum = nums[0] (not 0) to handle all-negative arrays?
Space optimization	Do you recognize that only the previous sum matters, no full DP array needed?
Subarray indices	Can you track and return the actual subarray, not just the sum?
Follow-up readiness	Can you extend to Maximum Product Subarray or Maximum Circular Subarray?

---

Step 1: Clarifying Questions

Taking a moment to ask smart questions before coding demonstrates structured thinking and prevents solving the wrong problem.

1. Can the array contain all negative numbers? Yes, and this is the most important edge case. For nums = [-3, -1, -2], the answer is -1 (the least negative single element), not 0. Confirming this determines how you initialize your result variable: max_sum = nums[0], never max_sum = 0.

2. Must the subarray be non-empty? Yes, the problem requires at least one element. This is consistent with the all-negative case: you must pick at least one number, even if all are negative.

3. Should I return the maximum sum, or the actual subarray? The base problem asks only for the sum. Tracking the actual subarray indices is a common follow-up. Confirm the simpler requirement first to avoid over-engineering, but be ready to add index tracking when asked.

4. Are there constraints on array length or value range? LeetCode allows up to 100,000 elements with values from -10,000 to 10,000. This rules out O(n²) for large inputs and confirms O(n) is the target.

5. Is a single element considered a valid subarray? Yes, a single element is a contiguous subarray of length 1. This matters for the all-negative case and the base case reasoning in both greedy and DP formulations.

---

Step 2: A First (Non-Optimal) Idea

The most natural starting point is brute force: enumerate every possible subarray by iterating over all pairs of start and end indices, compute each sum, and track the maximum.

def maxSubArray(nums):
    max_sum = nums[0, "medium"]
    n = len(nums)

    for i in range(n):
        current_sum = 0
        for j in range(i, n):
            current_sum += nums[j, "medium"]
            max_sum = max(max_sum, current_sum)

    return max_sum

This is O(n²) in time and O(1) in space. It’s correct and handles all edge cases cleanly, including all-negative arrays, because max_sum is initialized to nums[0]. For an array of 100,000 elements, however, this means 5 billion operations: unacceptable.

Going from O(n²) to O(n) requires a fundamentally different observation, not just a tighter loop.

---

Step 3: The Key Insight

The greedy observation at the heart of Kadane’s Algorithm: a negative running sum is a liability, not an asset. If carrying the current subarray’s sum into the next element makes things worse than starting fresh at that element, start fresh.

More precisely: at each index i, you have a binary choice:

• Extend the current subarray: take current_sum + nums[i]
• Start fresh: take just nums[i] alone

Which is better? Whichever is larger: max(current_sum + nums[i], nums[i]). If current_sum is negative, adding it to nums[i] gives you less than nums[i] alone, so discard it and start fresh. If current_sum is non-negative, extending is at least as good as starting fresh.

This can also be framed as a DP recurrence: let dp[i] be the maximum subarray sum ending at index i. Then:

dp[i] = max(nums[i], dp[i-1] + nums[i])

In plain English: the best subarray ending at i is either just nums[i] itself, or nums[i] appended to the best subarray ending at i-1. Since dp[i] only depends on dp[i-1], you don’t need the full array, just a single variable tracking the previous value. This is the space optimization that makes the algorithm O(1) space.

Two variables suffice: current_sum (the max subarray sum ending at the current index) and max_sum (the best seen so far across all ending positions). Update both at every step.

Tracing through the example makes the reset decision concrete:

⟲ = reset (start fresh instead of extending). At index 1, current_sum was -2. Extending to 1 would give -1, but starting fresh at 1 gives 1, so the algorithm discards the negative prefix. The same happens at index 3: current_sum has dropped back to -2, and starting fresh at 4 beats extending to 2. This second reset is where the winning subarray [4, -1, 2, 1] begins.

---

Step 4: Optimal Strategy (Kadane’s Algorithm)

The algorithm, step by step:

1. Initialize current_sum = nums[0], the best subarray ending at the first element is just that element.
2. Initialize max_sum = nums[0], the best sum seen so far. Never initialize to 0, that would miss all-negative arrays.
3. Iterate i from 1 to len(nums) - 1:
   • Update current_sum = max(nums[i], current_sum + nums[i]), extend or reset.
   • Update max_sum = max(max_sum, current_sum), track the global best.
4. Return max_sum.

The max(nums[i], current_sum + nums[i]) decision is equivalent to: if current_sum < 0, reset current_sum = nums[i]; otherwise, current_sum += nums[i]. Both formulations are equivalent and worth knowing.

---

Python Implementation

Kadane’s Algorithm, O(n) time, O(1) space

def maxSubArray(nums: list[int]) -> int:
    # Initialize both to the first element — handles all-negative arrays correctly
    current_sum = nums[0, "medium"]
    max_sum = nums[0, "medium"]

    for i in range(1, len(nums)):
        # Greedy choice: extend current subarray or start fresh at nums[i, "medium"]
        current_sum = max(nums[i], current_sum + nums[i])

        # Track the global maximum across all ending positions
        max_sum = max(max_sum, current_sum)

    return max_sum

Extended Version: Tracking Subarray Indices (Common Follow-Up)

def maxSubArray(nums: list[int]) -> int:
    current_sum = nums[0, "medium"]
    max_sum = nums[0, "medium"]

    start = 0          # Start of the current candidate subarray
    temp_start = 0     # Tracks where a new subarray begins on reset
    end = 0            # End of the best subarray found so far

    for i in range(1, len(nums)):
        if nums[i] > current_sum + nums[i]:
            # Starting fresh — reset current subarray to just nums[i, "medium"]
            current_sum = nums[i, "medium"]
            temp_start = i
        else:
            current_sum += nums[i, "medium"]

        if current_sum > max_sum:
            max_sum = current_sum
            start = temp_start   # Lock in the start of the best subarray
            end = i              # Lock in the end of the best subarray

    # The maximum subarray is nums[start:end+1, "medium"]
    return max_sum  # Or return nums[start:end+1] for the actual subarray

Key implementation notes worth calling out in an interview:

• nums[0] initialization, not 0. Initializing max_sum = 0 produces the wrong answer for all-negative arrays like [-3, -1, -2]. It returns 0 (implying an empty subarray) instead of -1. Since a non-empty subarray is required, always start with nums[0].
• max(nums[i], current_sum + nums[i]) vs. if current_sum < 0: reset. Both formulations are equivalent. The max() version is more idiomatic. The conditional version makes the decision logic more explicit. Choose whichever you find easier to explain.
• max_sum is updated after current_sum, not before. At each step, first determine the best subarray ending here, then check if it’s the global best.
• The index-tracking version requires a temp_start variable that resets whenever you start fresh, and a separate start that only updates when a new global maximum is found. Many candidates conflate these and produce wrong index bounds.

---

Time and Space Complexity

Operation	Complexity
Time	O(n)
Space	O(1)

Time: A single pass through the array. Each element is visited exactly once. Both max() calls are O(1). Total: O(n).

Space: Only two variables, current_sum and max_sum, regardless of input size. The DP framing would naively use an O(n) array, but the observation that dp[i] only depends on dp[i-1] reduces this to O(1). This is the space-optimized DP pattern that appears across many 1D DP problems.

A subtle note worth mentioning: Kadane’s algorithm can also be solved using divide-and-conquer in O(n log n) time and O(log n) space. While inferior asymptotically, interviewers sometimes ask for it to test breadth. The maximum subarray is either entirely in the left half, entirely in the right half, or crosses the midpoint.

---

Common Interview Mistakes

1. Initializing max_sum = 0 instead of nums[0]. This is the most common bug. For an all-negative array, no subarray has a non-negative sum, so returning 0 is wrong. The correct answer is the largest (least negative) single element. Always initialize to nums[0].

2. Initializing current_sum = 0 instead of nums[0]. Same problem. If the first element is the maximum subarray, starting current_sum at 0 means you’d need to add nums[0] on the first iteration, which the loop starting at index 1 skips.

3. Updating max_sum before current_sum. The correct order is: first compute the new current_sum (extend or reset), then check if it beats max_sum. Reversing the order means you’re comparing the previous iteration’s current_sum.

4. Not articulating the greedy decision before coding. Candidates who write the max() line without explaining the extend-or-reset decision appear to be transcribing a memorized solution. Always say: “At each element, I’m choosing between extending the current subarray or starting fresh, whichever gives the larger sum.”

5. Confusing this with the maximum subarray product problem. LeetCode #152 (Maximum Product Subarray) looks similar but requires tracking both a running maximum and minimum (because two negatives multiply to a positive). Mentioning this distinction proactively shows breadth.

6. Not recognizing the DP framing. Kadane’s is often presented purely as a greedy algorithm, but being able to frame it as dp[i] = max(nums[i], dp[i-1] + nums[i]) with space optimization demonstrates deeper understanding and connects it to the broader DP family.

7. Forgetting the all-negative array when tracing. During any trace-through, always include an example that triggers the reset behavior. A trace on [-2, 1, -3, 4, -1, 2, 1, -5, 4] that walks through the reset at 4 (where current_sum drops from -4 to 4) is far more convincing than one on an all-positive array.

---

What a Strong Candidate Sounds Like

“At each position, I have a binary choice: extend the current subarray by including nums[i], or start a brand new subarray at nums[i]. I should extend if the running sum is non-negative, it can only help. I should start fresh if the running sum is negative, it would drag down whatever comes next.”

“This greedy decision gives me: current_sum = max(nums[i], current_sum + nums[i]). I track the global maximum separately as max_sum. Both are initialized to nums[0], not 0, so I correctly handle all-negative arrays.”

“This is also expressible as a DP recurrence: dp[i] = max(nums[i], dp[i-1] + nums[i]). Since dp[i] only depends on dp[i-1], I can reduce the space to O(1) with just two variables instead of a full array.”

“Single pass, O(n) time, O(1) space. Let me trace through the example to verify the reset behavior before coding.”

---

Example Interview Dialogue

Interviewer: Find the maximum sum subarray in an integer array.

Candidate: Quick clarification: can the array be all negative, and must I return the sum rather than the subarray itself?

Interviewer: Yes, all negative is possible. Return the sum.

Candidate: Important, that means I initialize my result to nums[0], not 0. For all-negative inputs, 0 would be wrong since an empty subarray isn’t allowed. My approach: at each element, decide to extend the current subarray or start fresh, whichever is larger. If the running sum goes negative, it can only hurt future elements, so I reset it. I track the global max separately. This is Kadane’s algorithm: O(n) time, O(1) space.

Interviewer: Can you frame this as dynamic programming?

Candidate: Yes. Define dp[i] as the maximum subarray sum ending at index i. The recurrence is dp[i] = max(nums[i], dp[i-1] + nums[i]): either start fresh at nums[i] or extend the best subarray ending at i-1. Since each state only depends on the previous one, I replace the full DP array with a single variable current_sum. The answer is the maximum across all dp[i] values, tracked in max_sum.

Interviewer: How would you also return the actual subarray, not just the sum?

Candidate: I’d track a temp_start index that resets whenever current_sum resets to nums[i], and a locked start and end that update only when current_sum beats max_sum. The key is having two separate start indices: one that resets eagerly on every discard, and one that only commits when a new global max is confirmed. Same O(n) time, O(1) space, just three extra integer variables.

Interviewer: What about the maximum product subarray?

Candidate: That’s LeetCode #152. Products are trickier because a negative times a negative becomes positive, so a very negative running product could become very positive if multiplied by another negative. I’d track both a max_product and a min_product at each step. At each element I take max(nums[i], max_product * nums[i], min_product * nums[i]) for the new max, and correspondingly for the new min. Same O(n) time and O(1) space, but two running values instead of one.

---

Related Problems to Practice

Maximum Subarray is the entry point for a family of subarray optimization problems, all built on the same greedy/DP thinking:

Problem	How It Relates
#152. Maximum Product Subarray	Same structure, but tracks both max and min running products due to sign flips
#918. Maximum Sum Circular Subarray	Maximum subarray that can wrap around. Uses Kadane’s twice with an inversion trick
#121. Best Time to Buy and Sell Stock	Equivalent problem: max gain over a price array is the max subarray of day-to-day differences
#560. Subarray Sum Equals K	Prefix sum + hash map to count subarrays summing to a target. Related subarray reasoning
#1749. Maximum Absolute Sum of Any Subarray	Max of maximum subarray sum and absolute value of minimum subarray sum. Applies Kadane’s twice

The connection between Maximum Subarray and Best Time to Buy and Sell Stock (#121) is worth calling out: if you convert the stock prices to a daily difference array (prices[i] - prices[i-1]), the maximum subarray of that array is exactly the maximum profit. Knowing this bridge shows structural depth.

---

Practice This in a Mock Interview

Reading through this explanation makes Kadane’s algorithm feel elegant and obvious. The greedy reset decision is intuitive once you see it. But this problem has a consistent failure mode in interviews: candidates who know the algorithm initialize max_sum = 0 (forgetting the all-negative case), swap the update order, or can’t explain the DP framing when an interviewer pushes for it.

The explanation always sounds easier than the execution. The only way to make Kadane’s feel truly automatic, initialization correct, order right, greedy decision articulated clearly, all-negative trace handled, is to write it from scratch under timed conditions, narrate the logic out loud, and field follow-up questions about the DP formulation and index tracking.

Start a mock interview for Maximum Subarray on Intervu.

Further reading:

• How to Prepare for a Coding Interview in 2026, the complete roadmap
• Why LeetCode alone isn’t enough, and what to practice instead
• Data Structures for Coding Interviews, the complete guide
• Practice any LeetCode problem as a live mock interview
• The Grind 75 Pathway, a structured study plan with AI practice links
• Browse all walkthroughs on GitHub, condensed solutions with code