Skip to main content

53. Maximum Subarray

mediumAsked at IBM

Maximum Subarray is IBM's Kadane's-algorithm screener. The interviewer is grading whether you can derive Kadane's by stating the 'extend-or-restart' decision rule, ship it in O(n) with O(1) space, and articulate how it generalizes to the 2D variant.

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

Source citations

Public interview reports confirming this problem appears in IBM loops.

  • Glassdoor (2026-Q1)— Recurring IBM SWE-2 / SWE-3 onsite problem.
  • LeetCode (2026-Q1)— Top-20 IBM-tagged problem.
  • GeeksforGeeks (2025-12)— Listed in IBM interview-experience archive with Kadane's variant follow-ups.

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: [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 — every subarray

Two nested loops over all (i, j) pairs, accumulating the sum.

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: Trivial to derive. n^2 with the running sum is the smarter brute force (vs. n^3 with a separate sum loop). Times out at 10^5 — useful only as the starting point.

2. Kadane's algorithm (optimal)

Walk once. At each index, the best subarray ending here is either (a) extend the previous best subarray, or (b) start fresh at this element. Take the max.

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

Tradeoff: O(n) time and O(1) space — the canonical answer. The invariant 'bestEndingHere is the largest contiguous sum that ends at index i' is the whole problem; once you state it, the recurrence is obvious.

3. Divide and conquer

Recursively split the array; the answer is max(left half best, right half best, best subarray crossing the middle).

Time
O(n log n)
Space
O(log n) stack
function maxSubArrayDC(nums) {
  const solve = (lo, hi) => {
    if (lo === hi) return nums[lo];
    const mid = lo + Math.floor((hi - lo) / 2);
    const leftBest = solve(lo, mid);
    const rightBest = solve(mid + 1, hi);
    let leftSum = -Infinity;
    let acc = 0;
    for (let i = mid; i >= lo; i--) {
      acc += nums[i];
      if (acc > leftSum) leftSum = acc;
    }
    let rightSum = -Infinity;
    acc = 0;
    for (let i = mid + 1; i <= hi; i++) {
      acc += nums[i];
      if (acc > rightSum) rightSum = acc;
    }
    return Math.max(leftBest, rightBest, leftSum + rightSum);
  };
  return solve(0, nums.length - 1);
}

Tradeoff: Slower than Kadane but a great senior-loop response when asked 'how would you parallelize this?' — the divide-and-conquer structure parallelizes naturally. Mention it only as a follow-up answer.

IBM-specific tips

IBM specifically grades the invariant statement on this problem. Say 'at each index i, the best subarray ending at i is either nums[i] alone or the previous best extended by nums[i]; we take the max.' That single sentence is the rubric checkbox. Jumping straight to `Math.max(nums[i], bestEndingHere + nums[i])` without the narration looks memorized.

Common mistakes

  • Initializing bestSoFar to 0 — wrong for all-negative inputs (e.g., [-1, -2] should return -1, not 0).
  • Confusing bestEndingHere (rolling) with bestSoFar (global) — they are different variables.
  • Returning the subarray itself when only the sum was requested.
  • Forgetting that the subarray must be CONTIGUOUS — non-contiguous max-sum has a different (simpler) answer.

Follow-up questions

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

  • Return the actual subarray, not just the sum.
  • Maximum Sum Circular Subarray (LeetCode 918).
  • 2D Kadane — largest sum rectangle in a matrix.
  • Maximum Product Subarray (LeetCode 152) — sign-tracking variant.

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 is the all-negative case the most common bug?

Because the textbook intuition 'sum up positive contributions' breaks. If every element is negative, you still must return the single largest (least-negative) element. Initializing both rolling variables with nums[0] handles this; initializing with 0 silently gives wrong answers.

When does IBM ask the divide-and-conquer variant?

Almost never in the base problem — it's strictly worse than Kadane. But it shows up as a follow-up when the interviewer pivots to 'how would you parallelize this for a 10 TB array?' Then the recursive structure becomes the answer because each half can be solved on a separate worker.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →