Skip to main content

53. Maximum Subarray

easyAsked at DRW

DRW frames Maximum Subarray as a drawdown-analysis problem: find the contiguous period with the maximum cumulative return. Kadane's algorithm is the expected answer — and DRW will ask you to extend it to track the actual window start and end indices, then to compute it over a live return stream.

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

Source citations

Public interview reports confirming this problem appears in DRW loops.

  • Glassdoor (2026-Q1)— DRW SWE candidates report Maximum Subarray as a phone-screen staple, with interviewers quickly pivoting to the subarray-index extension.
  • Blind (2025-11)— DRW interview threads cite this problem as a gateway to sliding-window and streaming-aggregation questions common in the firm's analytics pipelines.

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: Subarray [4,-1,2,1] has the largest sum = 6.

Example 2

Input
nums = [1]
Output
1

Explanation: Single element.

Example 3

Input
nums = [5,4,-1,7,8]
Output
23

Explanation: The entire array is the optimal subarray.

Approaches

1. Kadane's algorithm

Walk the array. At each index, decide: extend the current subarray or start fresh (take the current element alone). Track the global maximum.

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

Tradeoff: O(n) time, O(1) space — optimal. This is the only acceptable approach at DRW. Be ready to extend it to also return the subarray's start and end indices.

2. Kadane's with index tracking

Track the start of the current candidate subarray and update start/end whenever a new maximum is found.

Time
O(n)
Space
O(1)
function maxSubArrayWithIndices(nums) {
  let currentSum = nums[0], maxSum = nums[0];
  let start = 0, tempStart = 0, end = 0;
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] > currentSum + nums[i]) {
      currentSum = nums[i];
      tempStart = i;
    } else {
      currentSum += nums[i];
    }
    if (currentSum > maxSum) {
      maxSum = currentSum;
      start = tempStart;
      end = i;
    }
  }
  return { maxSum, start, end };
}

Tradeoff: Same asymptotic complexity, adds constant-factor tracking overhead. DRW almost always asks for this extension — code it proactively.

DRW-specific tips

Frame the solution in trading terms: 'I'm computing the maximum cumulative return period — this is the inverse of maximum drawdown analysis.' DRW interviewers respond well to this framing. After the base solution, expect: 'What if the return stream is live and you want the maximum subarray sum over the last k elements?' — that is the sliding-window maximum variant. Also: 'What if values can repeat and you want the maximum circular subarray?' (LC 918 — subtract the minimum subarray from the total sum).

Common mistakes

  • Initializing currentSum and maxSum to 0 instead of nums[0] — fails on all-negative arrays.
  • Resetting currentSum to 0 instead of nums[i] when starting fresh — off-by-one in the new subarray.
  • Not tracking the subarray indices when the interviewer will certainly ask for them.
  • Using a divide-and-conquer approach without noting it is O(n log n) and less efficient than Kadane's.

Follow-up questions

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

  • Maximum Sum Circular Subarray (LC 918) — the subarray can wrap around; solution uses the minimum subarray complement.
  • How would you compute this over a sliding window of size k in O(n) total?
  • What is the expected maximum subarray sum for a length-n array of i.i.d. standard normal returns?

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 Kadane's algorithm work?

At each position, the maximum subarray ending here is either the current element alone (if extending would decrease the sum) or the current element plus the best subarray ending at the previous position. This local optimal choice yields the global optimum.

What about all-negative arrays?

The answer is the single largest (least negative) element. Kadane's handles this correctly only if you initialize currentSum and maxSum to nums[0], not 0.

How does this relate to DRW's risk systems?

Maximum drawdown — the peak-to-trough decline in a strategy's value — is the dual of maximum subarray sum. DRW's risk analytics compute both continuously over rolling windows.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →