Skip to main content

53. Maximum Subarray

easyAsked at Gusto

Find the contiguous subarray with the largest sum (Kadane's algorithm). Gusto asks this to see if you can articulate a greedy decision rule clearly — 'extend the current subarray or start fresh' — before writing a single line.

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

Source citations

Public interview reports confirming this problem appears in Gusto loops.

  • Glassdoor (2026-Q1)— Reported as an easy greedy problem in Gusto SWE onsite rounds with a follow-up asking candidates to return the subarray itself.
  • Blind (2025-10)— Gusto interview threads cite Maximum Subarray as a classic Kadane test used to filter for algorithmic intuition.

Problem

Given an integer array nums, find the subarray with the largest sum and return its sum. A subarray is a contiguous part of an array.

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

Example 3

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

Explanation: The entire array sums to 23, which is the maximum.

Approaches

1. Kadane's algorithm (greedy)

Track currentSum: extend by nums[i] if it helps, otherwise start a new subarray from nums[i]. Track globalMax across all steps.

Time
O(n)
Space
O(1)
function maxSubArray(nums) {
  let currentSum = nums[0];
  let globalMax = nums[0];
  for (let i = 1; i < nums.length; i++) {
    // either extend or start fresh at nums[i]
    currentSum = Math.max(nums[i], currentSum + nums[i]);
    globalMax = Math.max(globalMax, currentSum);
  }
  return globalMax;
}

Tradeoff: O(n) time, O(1) space, single pass. Initialise both variables with nums[0] to handle the all-negative array edge case — no need for a separate guard.

2. Divide and conquer

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

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

Tradeoff: O(n log n) — slower than Kadane but demonstrates recursive decomposition. Gusto may ask for it as a follow-up to assess versatility.

Gusto-specific tips

State Kadane's decision rule before coding: 'At each element, the best subarray ending here either starts fresh at this element, or extends the previous best subarray — whichever is larger.' Initialise with nums[0] not 0 — the all-negative case (e.g. [−3, −1, −2]) must return −1, not 0. Gusto may ask you to track the start and end indices of the subarray as a follow-up.

Common mistakes

  • Initialising globalMax to 0 — fails when all elements are negative (answer must be the largest single element, not 0).
  • Initialising globalMax to -Infinity but currentSum to 0 — still misses the all-negative case.
  • Starting the loop at i=0 and double-counting the first element.
  • Confusing Maximum Subarray (contiguous) with Maximum Subsequence (non-contiguous, which is just the sum of all positives).

Follow-up questions

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

  • Return the actual subarray (indices), not just its sum.
  • What if the array wraps around (circular)? (LC 918 — Maximum Sum Circular Subarray.)
  • How would you handle a 2D matrix version? (LC 363 — Max Sum of Rectangle.)

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 is the greedy choice correct?

If currentSum becomes negative, it can only drag down any future subarray. It's always better to start fresh. A negative prefix can never help a suffix.

What is the answer for an array of a single negative number?

That number itself. Both currentSum and globalMax are initialised to nums[0], so the loop doesn't execute and the correct answer is returned.

Is there an O(n) divide-and-conquer?

No. The cross-sum computation at each level requires O(n) work total per level, giving O(n log n) overall.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →