Skip to main content

53. Maximum Subarray

mediumAsked at Netflix

Given an integer array, find the contiguous subarray with the largest sum and return that sum. Netflix asks this on the warm-up screen to confirm you know Kadane's algorithm and can articulate the 'extend or restart' decision.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Netflix loops.

  • Glassdoor (2026-Q1)— Netflix new-grad and L4 reports cite this as the 10-minute warm-up before a harder follow-up.
  • Blind (2025-11)— Netflix SWE writeups describe Kadane narration ('extend vs restart') as the explicit signal.

Problem

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

Constraints

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

Examples

Example 1

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

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

Example 2

Input
nums = [1]
Output
1

Example 3

Input
nums = [5,4,-1,7,8]
Output
23

Approaches

1. Brute-force every subarray

Try every (i, j) start/end; sum the subarray; track the max.

Time
O(n^2)
Space
O(1)
function maxSubArrayBrute(nums) {
  let best = nums[0];
  for (let i = 0; i < nums.length; i++) {
    let s = 0;
    for (let j = i; j < nums.length; j++) {
      s += nums[j];
      best = Math.max(best, s);
    }
  }
  return best;
}

Tradeoff: Conceptually clear and O(1) space, but O(n^2) at n = 10^5 is 10^10 ops — TLE. Useful as the contrast for Kadane.

2. Kadane's algorithm (optimal)

Maintain cur = best sum ending at i. At each step, cur = max(nums[i], cur + nums[i]). Track the global max.

Time
O(n)
Space
O(1)
function maxSubArray(nums) {
  let cur = nums[0], best = nums[0];
  for (let i = 1; i < nums.length; i++) {
    cur = Math.max(nums[i], cur + nums[i]);
    best = Math.max(best, cur);
  }
  return best;
}

Tradeoff: O(n) at O(1) space. The cur recurrence is the 'extend or restart' decision: if adding nums[i] to the prior best is worse than starting fresh at nums[i], restart.

3. Divide and conquer

Recursively compute best subarray entirely in left half, entirely in right half, and crossing the midpoint. Return the max of the three.

Time
O(n log n)
Space
O(log n) recursion stack
function maxSubArrayDC(nums) {
  function helper(l, r) {
    if (l === r) return nums[l];
    const mid = (l + r) >> 1;
    const leftMax = helper(l, mid);
    const rightMax = helper(mid + 1, r);
    let leftSum = -Infinity, s = 0;
    for (let i = mid; i >= l; i--) { s += nums[i]; leftSum = Math.max(leftSum, s); }
    let rightSum = -Infinity; s = 0;
    for (let i = mid + 1; i <= r; i++) { s += nums[i]; rightSum = Math.max(rightSum, s); }
    return Math.max(leftMax, rightMax, leftSum + rightSum);
  }
  return helper(0, nums.length - 1);
}

Tradeoff: Slower than Kadane but the canonical follow-up question. Worth knowing if the interviewer asks 'what if the data is streaming from two sides?' — divide-and-conquer generalizes to segment trees for online updates.

Netflix-specific tips

Netflix interviewers want you to articulate Kadane's 'extend or restart' decision in plain English BEFORE writing the code. Say: 'At each index, I either extend my current run or start fresh at this element — whichever is bigger.' That one sentence carries the entire algorithm. Be ready for the divide-and-conquer follow-up; it's the standard probe for whether you can generalize.

Common mistakes

  • Initializing best = 0 instead of nums[0] — fails on arrays of all negatives.
  • Returning cur instead of best at the end — misses the case where the maximum subarray ended mid-array.
  • In the divide-and-conquer version, off-by-one in the cross-midpoint scan (forgetting to include the midpoint on one side).

Follow-up questions

An interviewer at Netflix may pivot to one of these next:

  • Maximum Product Subarray (LC 152) — same shape, but negatives make 'extend or restart' more nuanced.
  • Maximum Subarray with at most k elements removed.
  • Return the actual subarray, not just the sum.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why does Kadane's algorithm work?

Because the best subarray ending at index i either includes the best subarray ending at i-1 (and extends it) or starts fresh at i. There's no other option. The recurrence cur = max(nums[i], cur + nums[i]) captures exactly this choice.

Is the divide-and-conquer version ever preferable?

Practically no — Kadane is O(n) and dead simple. But the D&C version generalizes to segment trees for online range-max-subarray queries, which Kadane can't do.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill Maximum Subarray and other Netflix interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →