Skip to main content

48. Maximum Subarray

mediumAsked at Plaid

Find the contiguous subarray with the largest sum. Plaid asks this because finding the highest-net-deposit window in a transaction series uses exactly this primitive — Kadane's algorithm.

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

Source citations

Public interview reports confirming this problem appears in Plaid loops.

  • Glassdoor (2025)— Plaid backend onsite — net-deposit-window variant.
  • Blind (2026)— Plaid SWE II OA.

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: [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. Check every subarray

Nested loop over (start, end) pairs; compute sum.

Time
O(n^2)
Space
O(1)
// Nested loops with running sum — O(n^2). Don't ship for n=10^5.

Tradeoff: Quadratic. TLE.

2. Kadane's algorithm

Walk once. At each index, decide: extend the current subarray, or start a new one. Track the best sum seen.

Time
O(n)
Space
O(1)
function maxSubArray(nums) {
  let curr = nums[0], 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. The recurrence curr = max(nums[i], curr + nums[i]) is the core of Kadane — extend if it helps, otherwise reset.

Plaid-specific tips

Plaid loves Kadane because it generalizes to the 'highest net deposit window' over a transaction stream. Bonus signal: name the algorithm by name and explain the recurrence in one sentence. Discuss the divide-and-conquer alternative as a stretch — useful when the array is partitioned across shards.

Common mistakes

  • Initializing best to 0 — fails on all-negative arrays.
  • Confusing the recurrence — adding nums[i] unconditionally even when curr is more negative than starting fresh.
  • Tracking start/end indices when only the sum is asked for.

Follow-up questions

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

  • Return the actual subarray, not just the sum.
  • Maximum product subarray (LC 152) — sign-flipping twist.
  • Maximum sum circular subarray (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 init both curr and best to nums[0]?

Handles all-negative arrays correctly. If best starts at 0 you'd return 0 for [-5], which is wrong.

Divide and conquer — when is it useful?

When the array is split across nodes in a distributed system. Each node returns (total, max-prefix, max-suffix, max-subarray), and the combiner merges them. That's how Plaid's chart-aggregation service computes max-net-deposit across shards.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →