Skip to main content

53. Maximum Subarray

easyAsked at Hugging Face

Find the contiguous subarray with the largest sum. Hugging Face uses Kadane's algorithm as a litmus test for greedy DP thinking — the same pattern used when identifying the highest-scoring span in extractive question-answering models.

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

Source citations

Public interview reports confirming this problem appears in Hugging Face loops.

  • Glassdoor (2025-11)— Reported in Hugging Face phone screen write-ups as a classic greedy/DP screening question.
  • Blind (2025-09)— Multiple Hugging Face interview reports cite Maximum Subarray as an early-round signal problem for ML engineers.

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

Example 2

Input
nums = [1]
Output
1

Explanation: Single element.

Example 3

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

Explanation: The entire array is the best subarray.

Approaches

1. Kadane's Algorithm

Track the running sum; if it drops below 0, reset it to 0 (start a new subarray). Maintain a global maximum at each step.

Time
O(n)
Space
O(1)
function maxSubArray(nums) {
  let currentSum = 0;
  let maxSum = -Infinity;
  for (const num of nums) {
    currentSum += num;
    maxSum = Math.max(maxSum, currentSum);
    if (currentSum < 0) currentSum = 0;
  }
  return maxSum;
}

Tradeoff: O(n) time, O(1) space — optimal. The reset-to-zero trick is elegant: a negative prefix can never help a future subarray, so it's always safe to discard it.

2. Divide and Conquer

Split the array in half. The answer is in the left half, the right half, or spans the midpoint. Recurse on halves and combine in O(n).

Time
O(n log n)
Space
O(log n)
function maxSubArray(nums) {
  function helper(l, r) {
    if (l === r) return nums[l];
    const mid = Math.floor((l + r) / 2);
    const leftMax = helper(l, mid);
    const rightMax = helper(mid + 1, r);
    // max crossing subarray
    let leftSum = -Infinity, sum = 0;
    for (let i = mid; i >= l; i--) { sum += nums[i]; leftSum = Math.max(leftSum, sum); }
    let rightSum = -Infinity; sum = 0;
    for (let i = mid + 1; i <= r; i++) { sum += nums[i]; rightSum = Math.max(rightSum, sum); }
    return Math.max(leftMax, rightMax, leftSum + rightSum);
  }
  return helper(0, nums.length - 1);
}

Tradeoff: O(n log n) — slower than Kadane's but demonstrates divide-and-conquer mastery. Mention it as an alternative if the interviewer asks for a different approach.

Hugging Face-specific tips

Explain Kadane's loop invariant: 'currentSum is the maximum sum of any subarray ending exactly at index i.' Hugging Face will appreciate connecting this to span extraction in reading comprehension models: 'The same greedy sweep finds the highest-scoring answer span in a token sequence — you accumulate score and reset when the running total goes negative.' This domain connection signals ML engineering depth.

Common mistakes

  • Initializing maxSum to 0 — fails for all-negative arrays; use -Infinity or nums[0].
  • Resetting currentSum before updating maxSum — you'll miss the element that pushed it negative.
  • Confusing subarray (contiguous) with subsequence (non-contiguous) — no skipping allowed.
  • Not handling the single-element edge case — a length-1 array always returns that element.

Follow-up questions

An interviewer at Hugging Face may pivot to one of these next:

  • Maximum Product Subarray (LC 152) — products can flip sign on negatives; track both min and max.
  • Return the actual subarray, not just the sum — track start and end indices.
  • If the array wraps around (circular array), how does the answer change? (LC 918 — maximum sum circular subarray)

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 initialize maxSum to -Infinity and not 0?

If all elements are negative, the best answer is the least-negative element. Initializing to 0 would incorrectly return 0.

What is the loop invariant of Kadane's algorithm?

After each iteration, currentSum holds the maximum sum of any subarray ending at the current index. maxSum holds the global maximum across all prior indices.

Can I reconstruct the subarray boundaries?

Yes — track start when resetting currentSum, and record end + start when updating maxSum. Adds O(1) extra bookkeeping.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →