Skip to main content

7. Maximum Subarray

easyAsked at Palantir

Find the contiguous subarray with the largest sum. Palantir asks this because Kadane's algorithm illustrates the running-state pattern they expect in streaming aggregations over time-series telemetry.

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

Source citations

Public interview reports confirming this problem appears in Palantir loops.

  • Glassdoor (2025-11)— Palantir FDE phone screen, framed as 'best contiguous P&L window'.
  • Blind (2026-Q1)— Asked at Palantir onsite, follow-up on divide-and-conquer.

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.

Example 2

Input
nums = [1]
Output
1

Example 3

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

Approaches

1. Enumerate all subarrays

For every (i, j) pair, sum nums[i..j] and track max.

Time
O(n^3) naive / O(n^2) with running sum
Space
O(1)
let best = -Infinity;
for (let i = 0; i < n; i++) {
  let sum = 0;
  for (let j = i; j < n; j++) { sum += nums[j]; best = Math.max(best, sum); }
}

Tradeoff: Quadratic at best. Misses the running-state insight.

2. Kadane's algorithm

Maintain 'best subarray ending at i'. Either extend the previous, or start fresh at nums[i]. Track global max as you go.

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: Single pass, O(1) space. The insight is recognizing that 'best ending HERE' has a clean recurrence — extend or restart.

Palantir-specific tips

Palantir grades Kadane's on whether you initialize best and curr to nums[0] (not 0) — they often slip an all-negative test case in. The bonus signal is articulating the recurrence: 'best ending at i' = max(nums[i], best ending at i-1 + nums[i]). Once you state that, the code writes itself. Mention that this is the streaming version of the divide-and-conquer approach — perfect for processing telemetry one tick at a time.

Common mistakes

  • Initializing best = 0 — fails on all-negative inputs.
  • Forgetting to update best AFTER updating curr — gets stale max.
  • Trying prefix-sum approach without realizing it's still O(n) — works but less elegant.

Follow-up questions

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

  • Return the actual subarray bounds, not just the sum.
  • Maximum subarray sum with at most one deletion.
  • Maximum product subarray (LC 152) — Kadane variant that tracks min too (because of negative numbers).

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

What's the divide-and-conquer version?

Split the array; the answer is either entirely in the left half, entirely in the right, or crosses the midpoint. The crossing case is O(n) per level, giving O(n log n) total. Kadane's beats it asymptotically but D&C generalizes to segment trees for range queries.

Does Kadane's work for empty subarrays?

Standard LC 53 requires a non-empty subarray. If you allow empty (sum = 0), initialize best = 0 and add a max(0, ...) clamp. Be explicit with the interviewer.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →