Skip to main content

10. Maximum Subarray

easyAsked at Snap

Find the contiguous subarray with the largest sum. Snap uses this to verify you know Kadane's algorithm and can recognize a 1D running-sum DP without prompting.

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

Source citations

Public interview reports confirming this problem appears in Snap loops.

  • Glassdoor (2026-Q1)— Reported as a Snap onsite DP entry-point question.
  • Reddit r/cscareerquestions (2025)— Snap interns often see this followed by 'Maximum Product Subarray.'

Problem

Given an integer array nums, find the contiguous subarray (containing at least one number) which has 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: [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

Sum every (i, j) pair using a nested loop.

Time
O(n^2)
Space
O(1)
function maxSubArray(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) — too slow for 10^5 inputs.

2. Kadane's algorithm (optimal)

Track the best subarray sum ending at index i: either extend (best_so_far + nums[i]) or restart (nums[i]). Keep a global max of those.

Time
O(n)
Space
O(1)
function maxSubArray(nums) {
  let best = nums[0];
  let curr = 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, constant space. The 'extend or restart' insight is the canonical DP starter pattern.

Snap-specific tips

Snap values the 'either extend or restart' framing because it generalizes to streaming computations on view-counts and engagement metrics. Bonus: mention the divide-and-conquer variant (O(n log n)) since Snap interviewers sometimes ask about parallelization across shards.

Common mistakes

  • Initializing best to 0 — fails on all-negative arrays.
  • Updating curr after best — misses single-element max.
  • Using a sliding window — windows assume non-negativity and don't apply here.

Follow-up questions

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

  • Maximum Product Subarray (LC 152) — track both min and max.
  • Maximum Sum Circular Subarray (LC 918).
  • Return the actual subarray, not just the sum.

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 restarting the right choice when curr + nums[i] < nums[i]?

It means the running prefix is dragging the sum down — discarding it and starting fresh from nums[i] is always at least as good.

Does this work for empty arrays?

No — the problem guarantees at least one element. Trying to seed best with -Infinity then iterating from 0 also works, but the prompt's invariant lets you skip the empty case.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →