Skip to main content

53. Maximum Subarray

mediumAsked at Bloomberg

Find the contiguous subarray with the largest sum. Bloomberg uses Kadane's algorithm as the gateway to dynamic-programming questions — they want to see you derive the recurrence (current_max = max(num, current_max + num)) on the board.

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

Source citations

Public interview reports confirming this problem appears in Bloomberg loops.

  • Glassdoor (2026-Q1)— Bloomberg SWE phone-screen reports cite Maximum Subarray as the canonical DP warm-up.
  • Blind (2025-12)— Bloomberg new-grad reports note Kadane's as the algorithm Bloomberg specifically asks you to derive.

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. Kadane's algorithm (optimal)

At each index, the best subarray ending here is either nums[i] alone or nums[i] + (best ending at i-1). Track the running max.

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

Tradeoff: The textbook DP-in-O(1)-state answer. Bloomberg interviewers explicitly want you to derive the recurrence aloud.

2. Divide and conquer

Recursively find the max subarray in left half, right half, and crossing the middle. Return the max.

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

Tradeoff: Slower than Kadane's but worth mentioning to show breadth. Bloomberg sometimes asks 'what if this was a follow-up generalization?' — DC opens that door.

Bloomberg-specific tips

Bloomberg grades on the DERIVATION, not the memorized formula. Say out loud: 'at each index, the best subarray ending here either starts fresh at nums[i] or extends the previous one.' That insight is what they're checking.

Common mistakes

  • Initializing currentMax = 0 (wrong if all nums are negative — should init to nums[0]).
  • Initializing globalMax = 0 (same trap).
  • Forgetting the case where the entire array is negative — the answer is the single largest negative number.

Follow-up questions

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

  • Maximum Product Subarray (LC 152) — track max + min because negatives flip.
  • Maximum Sum Circular Subarray (LC 918) — Kadane's + total - min-subarray trick.
  • Best Time to Buy and Sell Stock (LC 121) — same shape, different framing.

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 must the result be at least nums[i] alone?

Because the subarray must be non-empty. If nums[i] is positive but currentMax + nums[i] is even more positive, extend; otherwise restart at nums[i].

Will Bloomberg ask for the actual subarray indices?

Common follow-up. Track start/end as you update currentMax. Reset start when you 'restart' at nums[i].

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →