Skip to main content

53. Maximum Subarray

mediumAsked at Google

Find the contiguous subarray with the largest sum. Google asks this to see whether you arrive at Kadane's algorithm and can articulate the invariant: at index i, the best subarray ending here is either the current element alone or the current element extending the previous best.

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

Source citations

Public interview reports confirming this problem appears in Google loops.

  • Glassdoor (2026-Q1)— Google L3/L4 phone-screen warm-up; Kadane's is the expected answer.
  • Reddit r/cscareerquestions (2025-10)— Common Google new-grad onsite question.

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

Example 3

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

Approaches

1. Brute-force every subarray

Enumerate every (i, j) and compute the sum of nums[i..j]. 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];
      best = Math.max(best, sum);
    }
  }
  return best;
}

Tradeoff: Quadratic; uses the prefix-sum trick to avoid the inner O(n) so it's already n^2 not n^3. Mention this before going to Kadane's so the interviewer sees you noticed the optimization.

2. Kadane's algorithm (optimal)

At each index, the best subarray ending here is max(nums[i], curr + nums[i]). Track the global best.

Time
O(n)
Space
O(1)
function maxSubArray(nums) {
  let curr = nums[0];
  let best = 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: Linear time, O(1) space. The invariant — 'curr is the best subarray ending exactly here' — is what makes Kadane's elegant.

Google-specific tips

Google interviewers want the invariant articulated: 'At index i, I'm tracking the best subarray that ENDS at i. That's either the current element alone or curr extended by it.' If you write Kadane's without that articulation, you lose communication points even when the code is right. Expect a follow-up asking you to return the actual subarray bounds.

Common mistakes

  • Initializing best to 0 instead of nums[0] — fails when all elements are negative.
  • Confusing 'subarray' with 'subsequence' (subarray must be contiguous).
  • Forgetting to update best inside the loop, only tracking curr.

Follow-up questions

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

  • Return the actual subarray (start and end indices), not just the sum.
  • What if the array is circular? (Maximum Sum Circular Subarray, LC 918.)
  • What if we want the K largest non-overlapping subarrays?

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 Kadane's O(n) and not O(n^2)?

Each element is touched exactly once. The 'extend or restart' decision at each index is O(1).

What if all elements are negative?

Kadane's still works as long as best is initialized to nums[0], not 0. The answer is the largest single element.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →