Skip to main content

6. Maximum Subarray

easyAsked at Square

Find the contiguous subarray with the largest sum. Square tests Kadane's algorithm because the same running-state pattern shows up in their net-flow reconciliation jobs where you want the best contiguous window of debits vs credits.

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

Source citations

Public interview reports confirming this problem appears in Square loops.

  • Blind (2025-11)— Cash App Investing team phone screen.
  • LeetCode Discuss (2026-Q1)— Square Capital team onsite.

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 all subarrays

Try every (i, j) pair; sum and track max.

Time
O(n^2)
Space
O(1)
function maxSubArray(nums) {
  let best = -Infinity;
  for (let i = 0; i < nums.length; i++) {
    let s = 0;
    for (let j = i; j < nums.length; j++) {
      s += nums[j];
      if (s > best) best = s;
    }
  }
  return best;
}

Tradeoff: Quadratic. TLEs at 10^5.

2. Kadane's running sum

Maintain a 'best ending here' that either extends the previous segment or restarts at the current element. Track the global max.

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

Tradeoff: Linear. Insight: extending only helps when current > 0 — otherwise restart.

Square-specific tips

Square interviewers want you to explain Kadane's invariant in plain English ('current is the best subarray ending exactly at index i') before coding. Bonus signal: mention divide-and-conquer as an alternative even if you don't implement it — shows you know maxSubArray is the canonical D&C teaching example.

Common mistakes

  • Initializing current and best to 0 — fails on all-negative arrays.
  • Computing current = current + nums[i] without the max-with-nums[i] reset.
  • Returning the subarray itself when only the sum was asked.

Follow-up questions

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

  • Return the actual subarray indices, not just the sum.
  • What if you can skip at most one element (LC 1186)?
  • Maximum Subarray Sum 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

Why is initial value nums[0] and not 0?

The subarray must contain at least one number. For all-negative inputs, the answer is the single largest (least negative) element.

What's the divide-and-conquer complexity?

O(n log n) — three recursive halves: max in left, in right, and crossing the midpoint.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →