Skip to main content

53. Maximum Subarray

easyAsked at Glean

Glean asks this to test Kadane's algorithm — a greedy scan that mirrors how a search ranker maximizes relevance score over a contiguous window of query tokens.

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

Source citations

Public interview reports confirming this problem appears in Glean loops.

  • Glassdoor (2026-Q1)— Glean engineering interviewers list Maximum Subarray as a frequent warm-up that tests greedy-vs-DP thinking.
  • Blind (2025-11)— Cited in Glean SWE prep threads as an expected easy/medium that reveals whether candidates know Kadane's algorithm by name.

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 — the maximum subarray is the element itself.

Example 3

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

Explanation: The entire array is the optimal subarray.

Approaches

1. Kadane's algorithm

Maintain a running sum. If the running sum ever goes negative, reset it to 0 (it can only hurt future subarrays). Track the global maximum at each step.

Time
O(n)
Space
O(1)
function maxSubArray(nums) {
  let maxSum = nums[0];
  let currentSum = 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. This is the expected answer. Initializing both to nums[0] correctly handles all-negative arrays without a special case.

2. Divide and conquer

Split the array in half. The maximum subarray is either entirely in the left half, entirely in the right half, or crosses the midpoint. Solve recursively and merge.

Time
O(n log n)
Space
O(log n) call stack
function maxSubArray(nums) {
  function helper(lo, hi) {
    if (lo === hi) return nums[lo];
    const mid = Math.floor((lo + hi) / 2);
    const leftMax = helper(lo, mid);
    const rightMax = helper(mid + 1, hi);
    // max crossing subarray
    let leftCross = -Infinity, sum = 0;
    for (let i = mid; i >= lo; i--) { sum += nums[i]; leftCross = Math.max(leftCross, sum); }
    let rightCross = -Infinity; sum = 0;
    for (let i = mid + 1; i <= hi; 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 demonstrates a deeper algorithmic toolkit. Mention this approach only if the interviewer asks for an alternative strategy.

Glean-specific tips

Name the algorithm: 'I'll use Kadane's algorithm.' Glean engineers recognize it and it signals preparation. Then explain the core insight: a negative prefix can only reduce future sums, so you reset when the running total drops below zero. Tie it to the search context: it's like discarding a query fragment that actively hurts relevance before you continue matching.

Common mistakes

  • Initializing maxSum and currentSum to 0 instead of nums[0] — breaks for all-negative arrays, which must return the largest (least negative) single element.
  • Resetting currentSum to 0 instead of nums[i] when nums[i] alone is larger — Math.max(nums[i], currentSum + nums[i]) handles this automatically.
  • Forgetting the follow-up: return the subarray indices, not just the sum — track start and end indices when the optimum updates.
  • Using O(n²) brute force without acknowledging Kadane's — interviewers expect you to know the linear solution.

Follow-up questions

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

  • Return the actual subarray (indices) that achieves the maximum sum.
  • Maximum Product Subarray (LC 152) — products change sign with negatives; requires tracking both max and min running products.
  • What if the array is circular? (LC 918)

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

What does Kadane's algorithm guarantee?

At each index i, currentSum holds the maximum subarray sum ending at i. Taking the running max over all i gives the global answer.

Why does Math.max(nums[i], currentSum + nums[i]) work?

If currentSum is negative, extending the subarray by nums[i] gives currentSum + nums[i] < nums[i]. Starting fresh at nums[i] is better. This single expression captures the 'extend or restart' decision.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →