Skip to main content

53. Maximum Subarray

mediumAsked at Uber

Find the contiguous subarray with the largest sum (Kadane's algorithm). Uber asks this to test whether you can derive the linear recurrence — 'extend or restart' — without resorting to O(n^2) brute force.

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

Source citations

Public interview reports confirming this problem appears in Uber loops.

  • Glassdoor (2026-Q1)— Uber SWE phone-screen reports list Kadane as a recurring quick-hit.
  • Levels.fyi (2026-Q1)— Uber L4 reports include Maximum Subarray as the 'first medium' opener.

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: [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

Two nested loops over (i, j); inner loop sums from i to j.

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

Tradeoff: Acceptable to state out loud as the warm-up. Drop it once you know Kadane is the target.

2. Kadane (optimal, single pass)

At each i, the best subarray ending at i is either nums[i] alone or nums[i] extending the best one ending at i-1.

Time
O(n)
Space
O(1)
function maxSubArray(nums) {
  let best = nums[0];
  let cur = 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: Linear time, constant space. The 'extend or restart' framing is what makes it elegant — and what Uber interviewers want you to articulate.

3. Divide and conquer

Best subarray is in left half, right half, or crosses the middle. Recurse and combine.

Time
O(n log n)
Space
O(log n)
function maxSubArrayDC(nums) {
  function solve(l, r) {
    if (l === r) return nums[l];
    const m = (l + r) >> 1;
    const left = solve(l, m);
    const right = solve(m + 1, r);
    let crossLeft = -Infinity, sum = 0;
    for (let i = m; i >= l; i--) { sum += nums[i]; crossLeft = Math.max(crossLeft, sum); }
    let crossRight = -Infinity; sum = 0;
    for (let i = m + 1; i <= r; i++) { sum += nums[i]; crossRight = Math.max(crossRight, sum); }
    return Math.max(left, right, crossLeft + crossRight);
  }
  return solve(0, nums.length - 1);
}

Tradeoff: Worse than Kadane in big-O. Worth mentioning if the interviewer asks 'what if you couldn't use Kadane?' — that's the cue to pivot to D&C.

Uber-specific tips

Uber's bar on this is the 'extend or restart' framing. Say it explicitly: 'For each index i, the best subarray ending here is either nums[i] starting fresh, or nums[i] glued onto the best one ending at i-1. Take the max of those two.' That sentence beats writing the code without it.

Common mistakes

  • Initializing best to 0 — fails on all-negative inputs like [-1, -2, -3] where the answer is -1.
  • Forgetting that subarray means contiguous — subsequence is a different problem.
  • Returning the subarray instead of just the sum (this problem asks for the sum).

Follow-up questions

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

  • Maximum sum circular subarray (LC 918) — same Kadane plus total-sum minus min subarray.
  • Maximum product subarray (LC 152) — different recurrence: track both max and min because negatives flip.
  • 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 initialize best to nums[0] instead of 0?

Because the best subarray must contain at least one element. On all-negative input, initializing to 0 returns the wrong answer (0 instead of the least-negative).

Is divide-and-conquer ever the preferred answer?

Not for this problem in isolation. It's useful as a stepping stone toward segment trees if a follow-up asks 'what if I want range-max-subarray queries on a mutable array?'.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →