Skip to main content

7. Maximum Subarray

easyAsked at Coinbase

Find the contiguous subarray with the largest sum. Coinbase asks this to test the local-vs-global pattern — the same shape shows up when finding the most profitable contiguous holding window in price data.

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

Source citations

Public interview reports confirming this problem appears in Coinbase loops.

  • Glassdoor (2026-Q1)— Coinbase L4 onsite reports cite Kadane variants.
  • Blind (2025-12)— Frequently follows with 'apply to a series of P/L bars'.

Problem

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. A subarray is a contiguous part of an array.

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: 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. Check all subarrays

Nested loop, sum every (i, j) range, take max.

Time
O(n^2)
Space
O(1)
function maxSubArray(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: Quadratic. Use only to motivate the linear version.

2. Kadane's algorithm

Track current best sum ending at i. At each step, either extend the previous window or start fresh from nums[i]. Update global best.

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

Tradeoff: Single pass with constant extra memory. The local-vs-global insight: 'curr' is the best ending here, 'best' is the best ending anywhere seen so far.

Coinbase-specific tips

Coinbase wants both the recurrence and the financial-domain framing. Explain that this is the 'one trade window' problem — bonus signal if you mention how to extend to 'k transactions' (LC 188). They also probe initial value: starting curr at nums[0] (not 0) handles all-negative inputs.

Common mistakes

  • Initializing curr or best to 0 — fails on all-negative arrays.
  • Returning curr instead of best — curr can dip after the optimal window ends.
  • Forgetting that subarray must be non-empty — the prompt rules out the empty subarray of sum 0.

Follow-up questions

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

  • Return the subarray indices, not just the sum.
  • What if you can make at most k transactions? (LC 188)
  • What if values arrive as a stream — keep curr and best per tick.

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 max(nums[i], curr+nums[i]) instead of just curr+nums[i]?

If curr+nums[i] < nums[i], the previous window is dragging us down — restart from nums[i]. That's the local-vs-global decision.

How does divide-and-conquer compare?

D&C is O(n log n) and overkill. The only reason to mention it is to flex — Kadane is strictly better and shorter.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →