Skip to main content

7. Maximum Subarray

easyAsked at Datadog

Find the contiguous subarray with the largest sum. Datadog phrases this as 'find the peak metric burst' — Kadane's algorithm runs in a single pass and ports directly to a streaming aggregator over a metric window.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Recurring Datadog onsite. Often re-framed as 'find peak load window.'
  • Blind (2025-12)— Reported twice at Datadog NYC and Boston onsites.

Problem

Given an integer array nums, find the contiguous subarray (containing at least one number) which has 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 sum 6.

Example 2

Input
nums = [1]
Output
1

Example 3

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

Approaches

1. Brute-force all subarrays

Two nested loops; compute sum for every (i, j).

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 — won't survive a 10M-point Datadog query.

2. Kadane's algorithm (optimal)

Walk left to right. At each i, decide: extend the current subarray, or start fresh from i. Track the best seen.

Time
O(n)
Space
O(1)
function maxSubArray(nums) {
  let best = nums[0];
  let curr = 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, O(1) extra state. The DP recurrence is best[i] = max(nums[i], best[i-1] + nums[i]) — pure streaming-friendly.

Datadog-specific tips

Datadog interviewers will follow up with: 'Now make this a sliding-window over a stream — give me the max sum in the last N minutes.' Show that Kadane's doesn't directly handle windowed queries; you'd need a monotonic deque or a prefix-sum + min-prefix trick. Bonus: discuss how to handle all-negative inputs.

Common mistakes

  • Initializing curr = 0 and best = 0 — fails on all-negative inputs like [-3, -2, -5].
  • Missing the 'restart vs extend' choice — using best = curr + nums[i] always extends, ignoring negative prefixes.
  • Treating it as a sliding window — this is NOT a fixed-window problem; the subarray can be any contiguous range.

Follow-up questions

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

  • Maximum Subarray with Index — return [start, end] too.
  • Maximum Product Subarray (LC 152) — sign-tracking variant.
  • Sliding-Window Maximum Sum — fixed window size, monotonic deque.

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 initialize curr to nums[0]?

Initializing to 0 implicitly assumes an empty subarray is allowed. The problem requires at least one element, so all-negative inputs would otherwise return 0 incorrectly.

Can this be a sliding window?

No — sliding window requires a fixed or monotonic window. Kadane decides at each step whether to restart, which a window can't do.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →