Skip to main content

53. Maximum Subarray

mediumAsked at Pinterest

Maximum Subarray is Pinterest's go-to dynamic-programming warm-up: given an integer array, find the contiguous subarray with the largest sum. The interviewer wants to see you derive Kadane's algorithm from first principles, not recite it.

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

Source citations

Public interview reports confirming this problem appears in Pinterest loops.

  • Glassdoor (2026-Q1)— Pinterest SWE-new-grad phone-screen reports cite Maximum Subarray as a DP warm-up before harder ranking-related follow-ups.
  • LeetCode Pinterest tag (2026-Q1)— Listed on the Pinterest company-tagged problem list.

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: 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: check every subarray

Try every (i, j) start/end pair, sum the elements between 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: Easy to write; n = 10^5 means 10^10 ops which times out. Use this only to anchor the conversation, not as your final answer.

2. Kadane's algorithm (optimal)

Track the best sum ending at index i. At each step, either extend the previous best or start fresh from nums[i]. The overall answer is the max across all positions.

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: O(n) time and O(1) space. The key insight: the optimal subarray ending at i is either the optimal subarray ending at i-1 plus nums[i], or just nums[i] alone. Reset the running sum the moment it goes negative.

Pinterest-specific tips

Pinterest interviewers grade on the derivation: don't just write Kadane's, talk through it. 'If the best subarray ending at i-1 was already negative, starting fresh from i is strictly better' is the line they want to hear. Initialize current AND best with nums[0] (not 0) so all-negative arrays return the largest negative.

Common mistakes

  • Initializing best = 0 — fails on all-negative inputs like [-2, -1, -3].
  • Using prefix sums + min-prefix tracking when Kadane's is cleaner.
  • Forgetting to return current vs best — the answer is the max across the whole scan, not the final running sum.
  • Trying a divide-and-conquer O(n log n) when Kadane is O(n) — that's an interesting follow-up but not the canonical answer.

Follow-up questions

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

  • Return the subarray indices, not just the sum.
  • Handle circular arrays (max subarray that may wrap around).
  • Solve with divide-and-conquer in O(n log n) — what's the recursive structure?
  • Maximum product subarray instead of sum (different DP because of sign flips).

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Is Kadane's algorithm really considered DP?

Yes. The recurrence dp[i] = max(nums[i], dp[i-1] + nums[i]) is textbook 1D DP. Space optimization reduces it to a single variable.

What if Pinterest asks the circular variant as a follow-up?

Two cases: max non-circular (standard Kadane) or max circular = total sum - min subarray. Take the max of the two. Edge case: if all negatives, the circular case incorrectly returns 0; fall back to standard Kadane.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →