Skip to main content

53. Maximum Subarray

easyAsked at Anduril

Find the contiguous subarray with the largest sum. Anduril uses this to test Kadane's algorithm fluency — a classic greedy-DP technique that mirrors the running-maximum pattern used in signal processing and telemetry anomaly detection on autonomous platforms.

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

Source citations

Public interview reports confirming this problem appears in Anduril loops.

  • Glassdoor (2026-Q1)— Mentioned in Anduril SWE interview reports as a greedy/DP warm-up question.
  • Blind (2025-10)— Anduril coding threads cite Maximum Subarray as a high-frequency problem for demonstrating linear-scan thinking.

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: Subarray [4,-1,2,1] has the largest sum = 6.

Example 2

Input
nums = [1]
Output
1

Explanation: Single element, trivially the maximum.

Example 3

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

Explanation: Entire array sums to 23.

Approaches

1. Brute force

Try every subarray start and end pair, compute the sum, and track the maximum.

Time
O(n^2)
Space
O(1)
function maxSubArray(nums) {
  let maxSum = -Infinity;
  for (let i = 0; i < nums.length; i++) {
    let sum = 0;
    for (let j = i; j < nums.length; j++) {
      sum += nums[j];
      maxSum = Math.max(maxSum, sum);
    }
  }
  return maxSum;
}

Tradeoff: O(n^2). Demonstrate you know it, then pivot immediately.

2. Kadane's algorithm

At each index, decide whether to extend the current subarray or start a new one. currentSum = max(nums[i], currentSum + nums[i]).

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

Tradeoff: O(n) time, O(1) space. The core insight: if the running sum drops below the current element alone, discard the history and start fresh. Name the algorithm — interviewers reward it.

Anduril-specific tips

Name Kadane's algorithm and state the decision rule: 'If extending the current subarray gives less than starting fresh at this index, reset.' Anduril engineers connect this to sliding-window optimization in telemetry processing. A common follow-up is to return the actual subarray indices — track startIndex, tempStart, and endIndex alongside the sums. Expect questions about all-negative arrays: the answer is the least-negative element, not zero.

Common mistakes

  • Initializing maxSum to 0 — fails when all elements are negative; use nums[0] or -Infinity.
  • Not starting the loop at index 1 when you seed with nums[0] — this causes an off-by-one where index 0 is processed twice.
  • Returning the count of elements instead of the sum.
  • Forgetting to update maxSum inside the loop — updating only currentSum tracks the running subarray but loses track of the historical best.

Follow-up questions

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

  • Return the actual start and end indices of the maximum subarray.
  • Maximum product subarray (LC 152) — negative numbers make this harder because multiplying two negatives gives a positive.
  • How would you solve this for a circular array (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

What does 'contiguous' mean?

The elements must be adjacent in the original array — you can't skip indices.

Why is this called a DP problem if it looks greedy?

It's both. The DP recurrence is dp[i] = max(nums[i], dp[i-1] + nums[i]). Kadane's algorithm just computes it greedily in-place without storing the full dp array.

What if all elements are negative?

The answer is the maximum single element (the least-negative value). Kadane's handles this correctly when initialized with nums[0] instead of 0.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →