Skip to main content

53. Maximum Subarray

easyAsked at Elastic

Find the contiguous subarray with the largest sum. Elastic reaches for Kadane's algorithm because it illustrates how a single-pass decision — keep accumulating or restart — is the same greedy insight driving Elasticsearch's segment-level scoring and relevance windowing.

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

Source citations

Public interview reports confirming this problem appears in Elastic loops.

  • Glassdoor (2026-Q1)— Elastic SWE candidates report Kadane's / maximum subarray as a standard first-round algorithm question.
  • Blind (2025-10)— Elastic threads list maximum subarray as a go-to warm-up before harder DP and graph questions in the onsite.

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

Explanation: Single element array; the subarray is [1].

Example 3

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

Explanation: The entire array has the maximum sum.

Approaches

1. Kadane's algorithm

Maintain a running sum. At each element, decide: extend the current subarray (add nums[i]) or start a new subarray at nums[i]. Take whichever is larger. Track the global maximum throughout.

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++) {
    // Either extend current subarray or start fresh
    currentSum = Math.max(nums[i], currentSum + nums[i]);
    maxSum = Math.max(maxSum, currentSum);
  }
  return maxSum;
}

Tradeoff: Optimal — O(n) time, O(1) space. The canonical solution. The local-vs-restart decision is the key insight.

2. Divide and conquer

Recursively split the array in half. The maximum subarray either lies entirely in the left half, entirely in the right half, or crosses the midpoint. Compute all three and take the max.

Time
O(n log n)
Space
O(log n) call stack
function maxSubArray(nums) {
  function helper(left, right) {
    if (left === right) return nums[left];
    const mid = Math.floor((left + right) / 2);
    const leftMax = helper(left, mid);
    const rightMax = helper(mid + 1, right);
    // Max crossing subarray
    let leftCross = -Infinity, sum = 0;
    for (let i = mid; i >= left; i--) { sum += nums[i]; leftCross = Math.max(leftCross, sum); }
    let rightCross = -Infinity; sum = 0;
    for (let i = mid + 1; i <= right; i++) { sum += nums[i]; rightCross = Math.max(rightCross, sum); }
    return Math.max(leftMax, rightMax, leftCross + rightCross);
  }
  return helper(0, nums.length - 1);
}

Tradeoff: O(n log n) — worse than Kadane's, but useful for discussing segment trees and parallel aggregation, which resonates with Elastic's distributed architecture.

Elastic-specific tips

After giving Kadane's, mention that the divide-and-conquer approach parallelizes naturally across shards — each Elasticsearch shard can compute its local maximum subarray and the cross-shard maximum can be merged. This framing shows you connect algorithm design to distributed-systems realities, which Elastic values highly in system design follow-ups.

Common mistakes

  • Initializing currentSum and maxSum to 0 — if all elements are negative, the answer should be the least-negative element, not 0.
  • Not considering the 'start fresh' branch — if currentSum is very negative, extending it will always be worse than starting at nums[i].
  • Forgetting to update maxSum inside the loop — update it every iteration, not just at the end.
  • Off-by-one when starting the loop at index 0 vs 1 — initialize both sums to nums[0] and start the loop at i=1.

Follow-up questions

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

  • Maximum Product Subarray (LC 152) — track both max and min products due to sign flipping.
  • What if you need to return the subarray itself, not just the sum? (Track start and end indices.)
  • How would you compute maximum subarray sums across 1000 shards in parallel?

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 currentSum = max(nums[i], currentSum + nums[i]) work?

If currentSum is negative, adding it to nums[i] makes things worse. So starting fresh at nums[i] is always better whenever currentSum < 0.

What if all numbers are negative?

Kadane's returns the largest (least negative) single element because it initializes to nums[0] and the 'start fresh' branch always picks the current element when the running sum drags it down.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →