53. Maximum Subarray
mediumAsked at RobinhoodGiven 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 Sam K., 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
nums = [-2,1,-3,4,-1,2,1,-5,4]6Explanation: The subarray [4,-1,2,1] has the largest sum 6.
Example 2
nums = [1]1Example 3
nums = [5,4,-1,7,8]23Approaches
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.
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.