Skip to main content

53. Maximum Subarray

mediumAsked at Intel

Given an integer array, find the contiguous subarray with the largest sum. Intel asks because Kadane's algorithm is the textbook DP entry point — the candidate who derives it from the invariant 'best ending here' before writing code is the candidate who can later derive less-famous DPs from first principles.

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

Source citations

Public interview reports confirming this problem appears in Intel loops.

  • Glassdoor (2026-Q1)— Intel SWE-II onsite reports cite max-subarray as a recurring Kadane / DP ask.
  • GeeksforGeeks (2025-08)— Intel Interview Experience archives reference Kadane's algorithm as a 'must-know'.
  • LeetCode discuss (2025-12)— Intel-tagged in the company-frequency filter.

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

Example 3

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

Approaches

1. All subarrays (brute)

Enumerate every (i, j) with i <= j and sum nums[i..j].

Time
O(n^3) or O(n^2) with running sum
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];
      best = Math.max(best, sum);
    }
  }
  return best;
}

Tradeoff: Quadratic — fine for n <= 10^3, times out at 10^5.

2. Kadane's algorithm (optimal)

Track 'best subarray ending exactly at i'. Either extend the previous best-ending-here by nums[i], or start fresh at nums[i]. Take the max.

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

Tradeoff: Single pass, constant space, branch-friendly. The canonical answer. The key insight is the 'either extend or restart' choice at each index, which is the smallest possible DP state.

3. Divide and conquer (alternative)

Split the array. Max subarray is either entirely in the left half, entirely in the right half, or crosses the midpoint. Crossing case is a linear scan from the midpoint outward.

Time
O(n log n)
Space
O(log n) recursion
function maxSubArrayDC(nums) {
  function go(lo, hi) {
    if (lo === hi) return nums[lo];
    const mid = Math.floor((lo + hi) / 2);
    const leftMax = go(lo, mid);
    const rightMax = go(mid + 1, hi);
    // Cross-mid max
    let leftSum = -Infinity, sum = 0;
    for (let i = mid; i >= lo; i--) { sum += nums[i]; if (sum > leftSum) leftSum = sum; }
    let rightSum = -Infinity; sum = 0;
    for (let i = mid + 1; i <= hi; i++) { sum += nums[i]; if (sum > rightSum) rightSum = sum; }
    return Math.max(leftMax, rightMax, leftSum + rightSum);
  }
  return go(0, nums.length - 1);
}

Tradeoff: Slower asymptotically but useful when the interviewer says 'show me a divide-and-conquer'. Also parallelizable — each recursive call is independent, mappable across cores.

Intel-specific tips

Intel often pushes 'can you parallelize this for multiple cores?' as a follow-up. That's the lever for the divide-and-conquer version — left half, right half, and cross-midpoint all run independently, so it maps cleanly to a thread pool. Mentioning this unprompted lands the Intel-flavored systems signal.

Common mistakes

  • Initializing best and bestEndingHere to 0 — wrong when all numbers are negative (the answer should be the least negative).
  • Resetting bestEndingHere to 0 instead of nums[i] when it goes negative — same all-negative bug.
  • Forgetting the standalone best variable and using only bestEndingHere as the return — gives the best subarray ending at the LAST index, not anywhere.

Follow-up questions

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

  • Maximum Product Subarray (LC 152) — track max AND min ending here because a negative times a negative flips.
  • Maximum Sum Circular Subarray (LC 918) — wrap-around variant.
  • Maximum Subarray of size <= k — sliding window variant.
  • What if the array is so large you need to stream it across multiple machines? (Each machine computes (prefix, suffix, total, best) of its chunk; combine pairwise.)

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 does Kadane's algorithm work?

The optimal subarray ends at some index i. If we know the best subarray ending at each i, the global answer is the max over those n values. The 'extend or restart' choice at i is provably optimal because extending a negative-running sum can only hurt — better to restart from nums[i].

When would I actually use divide-and-conquer over Kadane's?

When you need parallelism. Kadane's is sequential — each iteration depends on the previous. The divide-and-conquer version has independent left/right subproblems, so it parallelizes across cores or maps naturally onto MapReduce.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →