Skip to main content

53. Maximum Subarray

mediumAsked at JPMorgan

Find the contiguous subarray with the largest sum. JPMorgan asks this on quant-research and equities-tech loops because the optimal Kadane's algorithm is one line of state and maps directly to 'largest cumulative P&L window' on a returns series.

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

Source citations

Public interview reports confirming this problem appears in JPMorgan loops.

  • Glassdoor (2026-Q1)— Recurring JPMorgan quant-research and equities-tech onsite problem.
  • LeetCode (2026-Q1)— Tagged JPMorgan on the LeetCode company tag page.
  • Blind (2025-11)— JPMC quant SDE write-up mentions Kadane as the first 30-minute coding round.

Problem

Given an integer array nums, find the contiguous subarray (containing at least one number) 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 (i, j) window

For every pair of indices i <= j, compute the sum of nums[i..j] and track the max.

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];
      if (sum > best) best = sum;
    }
  }
  return best;
}

Tradeoff: Correct but quadratic. Useful only as a sanity check while you reason your way to Kadane's. At n=10^5 this will TLE.

2. Kadane's algorithm (optimal)

Track best-ending-here as max(num, bestEndingHere + num). The global answer is the max over all positions of best-ending-here.

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: Single pass, O(1) state — the textbook answer. The cur = max(nums[i], cur + nums[i]) line encodes the key insight: either start fresh at nums[i] or extend the previous best.

3. Divide and conquer

Recurse on left half, right half, and the best crossing-the-midpoint subarray. Combine the three.

Time
O(n log n)
Space
O(log n) recursion
function maxSubArrayDnC(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 leftBest = -Infinity, sum = 0;
    for (let i = m; i >= l; i--) { sum += nums[i]; leftBest = Math.max(leftBest, sum); }
    let rightBest = -Infinity; sum = 0;
    for (let i = m + 1; i <= r; i++) { sum += nums[i]; rightBest = Math.max(rightBest, sum); }
    return Math.max(left, right, leftBest + rightBest);
  }
  return solve(0, nums.length - 1);
}

Tradeoff: Slower than Kadane but worth knowing — JPMorgan quant-research interviewers sometimes ask for the divide-and-conquer version specifically to test whether you can frame the cross-midpoint case.

JPMorgan-specific tips

On JPMorgan quant-research and quant-dev loops, the interviewer often follows up with 'and now imagine each element is a daily return — what does the answer mean?' (The answer: the largest drawdown-recovery window.) Stating that interpretation unprompted reads as 'understands finance' and routinely tips a marginal candidate over the bar.

Common mistakes

  • Initialising best to 0 — breaks on all-negative arrays where the correct answer is the single least-negative element.
  • Writing cur = max(0, cur + nums[i]) — that solves a slightly different problem (max with empty-subarray allowed) and gives 0 instead of the all-negative answer.
  • Tracking only one variable and trying to recover global max from it — you need both 'best ending here' and 'best so far'.
  • Forgetting the divide-and-conquer cross-midpoint walk must extend in both directions from the boundary.

Follow-up questions

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

  • Return the actual subarray bounds, not just the sum.
  • Maximum sum circular subarray (LC 918).
  • Maximum product subarray (LC 152) — track max and min because of sign flips.
  • K-concatenation maximum sum (LC 1191).
  • Largest sum of a contiguous subarray of length at most K.

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 cur = max(nums[i], cur + nums[i]) work?

It encodes the optimal-substructure invariant: the best subarray ending at i either starts at i (so cur = nums[i]) or extends the best subarray ending at i-1 (so cur = cur_prev + nums[i]). Take the larger. The global answer is the max over all positions of these per-position values.

Does JPMorgan accept the divide-and-conquer answer even though it is asymptotically worse?

Yes, especially if you can articulate why you would pick it (parallelisable, useful when the input is too large for a single machine). Lead with Kadane for correctness then mention the divide-and-conquer version if the interviewer probes for 'what if the input was distributed?'

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →