53. Maximum Subarray
mediumAsked at JPMorganFind 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 Sam K., 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
nums = [-2,1,-3,4,-1,2,1,-5,4]6Explanation: [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 (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.
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.