Skip to main content

53. Maximum Subarray

mediumAsked at Goldman Sachs

Find the contiguous subarray with the largest sum. Goldman Sachs uses Maximum Subarray to test whether you know Kadane's algorithm by name — the canonical O(n) DP that should come out from muscle memory.

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

Source citations

Public interview reports confirming this problem appears in Goldman Sachs loops.

  • Glassdoor (2026-Q1)— Goldman Sachs SWE and Strats reports cite Maximum Subarray as one of their top-5 most-asked DP questions.
  • LeetCode Discuss (2025-12)— Maximum Subarray sits in the top-5 of LeetCode's Goldman Sachs company tag.

Problem

Given an integer array nums, find the subarray with the largest sum, and return its sum. A subarray is a contiguous non-empty sequence of elements within 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: The subarray [4,-1,2,1] has the largest sum 6.

Example 2

Input
nums = [1]
Output
1

Example 3

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

Approaches

1. Brute-force every subarray

Try every start and end; sum them; track the max.

Time
O(n^2)
Space
O(1)
function maxSubArrayBrute(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];
      if (sum > best) best = sum;
    }
  }
  return best;
}

Tradeoff: O(n^2) with cumulative sum trick (O(n^3) without it). Times out at n = 10^5. Mention then move to Kadane.

2. Kadane's algorithm (optimal)

Maintain the best subarray ending at index i: currentSum = max(nums[i], currentSum + nums[i]). Track the overall best.

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

Tradeoff: Single pass, constant space. The invariant — cur = best subarray ending HERE — is the part Goldman wants articulated by name. Saying 'this is Kadane's' is itself worth a rubric point.

3. Divide and conquer

Recurse on left half, right half, and the best spanning the midpoint.

Time
O(n log n)
Space
O(log n)
function maxSubArrayDC(nums, l = 0, r = nums.length - 1) {
  if (l === r) return nums[l];
  const m = (l + r) >> 1;
  const left = maxSubArrayDC(nums, l, m);
  const right = maxSubArrayDC(nums, m + 1, r);
  let lc = -Infinity, sum = 0;
  for (let i = m; i >= l; i--) { sum += nums[i]; lc = Math.max(lc, sum); }
  let rc = -Infinity; sum = 0;
  for (let i = m + 1; i <= r; i++) { sum += nums[i]; rc = Math.max(rc, sum); }
  return Math.max(left, right, lc + rc);
}

Tradeoff: Slower than Kadane but the canonical divide-and-conquer demonstration. Mention this in senior interviews as a bonus — Goldman likes when candidates show alternate approaches.

Goldman Sachs-specific tips

Goldman Sachs interviewers will explicitly ask 'is this Kadane's?' — saying the name out loud signals you have the algorithm vocabulary they want. The follow-up at Goldman is usually 'return the actual subarray, not just the sum' — be ready to track start/end indices. For senior roles, expect the divide-and-conquer follow-up.

Common mistakes

  • Initializing best = 0 — fails when all nums are negative (best is the single least-negative element).
  • Using cur = cur + nums[i] without the max(nums[i], ...) — silently extends a negative cur forever.
  • Asking 'can the subarray be empty?' — no. The problem says non-empty.

Follow-up questions

An interviewer at Goldman Sachs may pivot to one of these next:

  • Return the actual subarray, not just the sum. (Track best-end and best-start indices alongside the sum.)
  • Maximum Product Subarray (LC #152) — multiplicative, requires tracking both max and min product.
  • Maximum Subarray Sum with Exactly K Elements — fixed-window variant.
  • Circular Maximum Subarray (LC #918) — wrap-around allowed.

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

Jay Kadane published it in 1984 as a linear-time DP for this exact problem. The name has stuck in interview prep because every textbook reproduces his 8-line algorithm. Saying 'Kadane' tells Goldman you've seen this in a textbook, not just on LeetCode.

What's the invariant being maintained?

cur is always the maximum subarray sum among all subarrays ending at the current index. best is the maximum of cur seen across all indices. Together they cover every possible subarray exactly once.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →