Skip to main content

53. Maximum Subarray

mediumAsked at Robinhood

Given an integer array, find the contiguous subarray with the largest sum. Robinhood asks this for two reasons: Kadane's algorithm is interview-classic and the daily-delta variant maps directly to best-trade-window questions on the trading side.

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

Source citations

Public interview reports confirming this problem appears in Robinhood loops.

  • Glassdoor (2026-Q1)— Robinhood SWE phone-screen reports list Maximum Subarray as a recurring 20-minute problem.
  • Blind (2025-12)— Robinhood new-grad trip reports cite Kadane's as a frequent warm-up.

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

For each (i, j) try the subarray sum; keep the running max.

Time
O(n^2) with running sum, O(n^3) naive
Space
O(1)
function maxSubArrayBrute(nums) {
  let best = nums[0];
  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: Quadratic. Mention it as the warm-up, then move to Kadane's.

2. Kadane's algorithm (optimal)

At each index, either extend the previous best-ending-here or start fresh. current = max(nums[i], current + nums[i]).

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

Tradeoff: O(n) time, O(1) space — the canonical answer. Kadane's invariant: 'current = best subarray sum ending exactly at index i.' Either extend or restart.

3. Divide and conquer

Split the array; the max subarray is either fully in the left half, fully in the right half, or crosses the midpoint.

Time
O(n log n)
Space
O(log n) recursion
function maxSubArrayDivide(nums) {
  function helper(lo, hi) {
    if (lo === hi) return nums[lo];
    const mid = (lo + hi) >> 1;
    const leftMax = helper(lo, mid);
    const rightMax = helper(mid + 1, hi);
    let crossLeft = -Infinity, sum = 0;
    for (let i = mid; i >= lo; i--) {
      sum += nums[i];
      crossLeft = Math.max(crossLeft, sum);
    }
    let crossRight = -Infinity;
    sum = 0;
    for (let i = mid + 1; i <= hi; i++) {
      sum += nums[i];
      crossRight = Math.max(crossRight, sum);
    }
    return Math.max(leftMax, rightMax, crossLeft + crossRight);
  }
  return helper(0, nums.length - 1);
}

Tradeoff: Worse than Kadane's but generalizes nicely to range queries. Show only if asked; Kadane's is the default.

Robinhood-specific tips

Robinhood interviewers want Kadane's directly. Don't reach for DP arrays — collapse to O(1) space. Articulate the invariant out loud: 'current is the best subarray sum ending exactly at index i; either extend or restart.' Be ready for the variant: 'what if all numbers are negative?' (Kadane's still works — current stays negative and best tracks the largest individual element).

Common mistakes

  • Initializing best = 0 — wrong for all-negative arrays where the answer is the largest negative.
  • Using current = max(0, current + nums[i]) — that's the 'best subarray with at least one positive prefix' variant, not the general one.
  • Returning the subarray itself instead of the sum (read the problem carefully).

Follow-up questions

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

  • Maximum Sum Circular Subarray (LC 918) — sum across the array boundary.
  • Maximum Product Subarray (LC 152) — same DP shape with min/max tracking.
  • K-Concatenation Maximum Sum (LC 1191) — virtual array repetition.
  • Return the indices, 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

What if all numbers are negative?

Kadane's returns the largest (least negative) single element. Initialize current = best = nums[0] so the running max never spuriously resets to 0.

Why Math.max(nums[i], current + nums[i])?

Because if current + nums[i] is worse than nums[i] alone, dropping everything before i is strictly better. The max picks the better of 'extend' vs 'restart at i'.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →