Skip to main content

53. Maximum Subarray

easyAsked at Citadel

Kadane's algorithm is a staple in quantitative finance: finding the highest-return contiguous window in a P&L series, identifying the best momentum run in a price series, or detecting the worst drawdown period (negate the array). Citadel interviewers expect you to name the algorithm, prove it greedy, and know the divide-and-conquer alternative.

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

Source citations

Public interview reports confirming this problem appears in Citadel loops.

  • Glassdoor (2026-Q1)— Citadel SWE candidates report Maximum Subarray as a common problem used to probe DP and greedy intuition in phone screens.
  • Blind (2025-09)— Citadel SWE threads specifically mention Kadane's algorithm as expected knowledge in coding rounds.

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 — the subarray is just [1].

Example 3

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

Explanation: The entire array is the best subarray.

Approaches

1. Kadane's algorithm (greedy DP)

At each position, decide: extend the current subarray or start fresh from this element. Keep a running maximum.

Time
O(n)
Space
O(1)
function maxSubArray(nums) {
  let curr = nums[0]; // max subarray ending at current index
  let best = nums[0]; // global maximum
  for (let i = 1; i < nums.length; i++) {
    curr = Math.max(nums[i], curr + nums[i]); // extend or restart
    best = Math.max(best, curr);
  }
  return best;
}

Tradeoff: O(n) time, O(1) space. The key insight: if curr < 0, adding any element to it makes the sum worse than starting fresh. This is the expected answer at Citadel — state the algorithm name explicitly.

2. Divide and conquer

Split the array at the midpoint. The maximum subarray either lies in the left half, the right half, or crosses the midpoint. For the crossing case, expand left and right from the midpoint greedily.

Time
O(n log n)
Space
O(log n) call stack
function maxSubArray(nums) {
  function helper(l, r) {
    if (l === r) return nums[l];
    const mid = (l + r) >> 1;
    const leftMax = helper(l, mid);
    const rightMax = helper(mid + 1, r);
    // cross-sum: extend from mid outward
    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) time — worse than Kadane's, but demonstrates divide-and-conquer thinking. Citadel may ask for this as a follow-up to test algorithmic breadth. Mention it proactively.

Citadel-specific tips

Explicitly name 'Kadane's algorithm' when you present it — Citadel interviewers appreciate precision. Then frame the greedy insight in financial terms: 'If my running P&L window has gone negative, I'm better off starting a new position today than holding the losing streak.' Expect the follow-up: 'How would you find the actual subarray indices, not just the sum?' Track start, end, and tempStart indices alongside curr and best.

Common mistakes

  • Initializing curr and best to 0 instead of nums[0] — this breaks when all elements are negative (the answer should be the least-negative element, not 0).
  • Using Math.max(0, curr + nums[i]) — same problem, this ignores all-negative inputs.
  • Not updating best after every iteration — only updating at the end picks up the wrong value.
  • Confusing the divide-and-conquer cross-sum: you must greedily expand from mid, not just take mid ± 1.

Follow-up questions

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

  • Maximum Product Subarray (LC 152) — track both max and min because negatives flip sign.
  • How do you return the actual subarray, not just the sum?
  • How would you find the maximum subarray sum where the subarray must have length at least k?

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 to nums[0] and not 0?

If all numbers are negative, the best subarray is the single least-negative element. Initializing to 0 would incorrectly return 0 (no-trade), which is not a valid subarray.

Is Kadane's DP or greedy?

Both framings are valid. DP: dp[i] = max subarray ending at i. Greedy: at each index, greedily decide whether to extend or restart. The recurrence and the greedy choice are equivalent.

What does this look like applied to a P&L series?

Each nums[i] is the daily return. Kadane's finds the highest-return contiguous holding period. Negate the array and run Kadane's to find the worst drawdown period.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →