53. Maximum Subarray

Q: Why initialize to nums[0] instead of 0?

Because the array can be entirely negative. If you initialize `best` to 0, you'd return 0 on input [-3, -1, -2], but the correct answer is -1 (the single largest element). Always initialize to `nums[0]`.

Q: Is Kadane's a 'DP' algorithm?

Yes — it's the textbook example of bottom-up DP with O(1) space. The DP table would be `cur[i] = max subarray ending at i`; the recurrence is `cur[i] = max(nums[i], cur[i-1] + nums[i])`. Since each `cur[i]` only depends on `cur[i-1]`, you collapse the array to a single variable.

mediumAsked at Cisco

Maximum Subarray at Cisco is the canonical Kadane's-algorithm problem. The interviewer is checking whether you reach for the O(n) one-pass scan with the running-max invariant rather than the brute-force O(n^2) double loop.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-19

Source citations

Public interview reports confirming this problem appears in Cisco loops.

Glassdoor (2026-Q1)— Cisco SDE-I and SDE-II reports cite Maximum Subarray as a 20-30 minute DP round.
Blind (2025-09)— Cisco interview thread lists this as a recurring Kadane's problem.

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

Explanation: Subarray [4,-1,2,1] has sum 6.

Example 2

Input

nums = [1]

Output

Example 3

Input

nums = [5,4,-1,7,8]

Output

Approaches

1. Brute-force double loop

Try every subarray [i, j], track the max sum across all pairs.

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: Quadratic, TLEs on the LeetCode upper bound (10^5). Useful only to show you can describe what you're maximizing before optimizing.

2. Kadane's algorithm (optimal)

Single pass. Maintain `cur` = best subarray sum ENDING at the current index. At each step: cur = max(nums[i], cur + nums[i]). Track the global max as you go.

Time: O(n)
Space: O(1)

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

Tradeoff: The canonical answer. The invariant: `cur` is the best subarray sum ending here. The decision per step — 'extend the previous subarray or start fresh at me' — is the whole algorithm. Cisco interviewers expect Kadane's by name.

3. Divide and conquer

Recursively find the max subarray in the left half, right half, and any subarray crossing the midpoint. Return the overall max.

Time: O(n log n)
Space: O(log n)

function maxSubArrayDC(nums) {
  function helper(lo, hi) {
    if (lo === hi) return nums[lo];
    const mid = (lo + hi) >> 1;
    const leftMax = helper(lo, mid);
    const rightMax = helper(mid + 1, hi);
    // Max subarray crossing mid
    let lSum = -Infinity, sum = 0;
    for (let i = mid; i >= lo; i--) {
      sum += nums[i];
      if (sum > lSum) lSum = sum;
    }
    let rSum = -Infinity;
    sum = 0;
    for (let i = mid + 1; i <= hi; i++) {
      sum += nums[i];
      if (sum > rSum) rSum = sum;
    }
    return Math.max(leftMax, rightMax, lSum + rSum);
  }
  return helper(0, nums.length - 1);
}

Tradeoff: Slower than Kadane's but a great signal that you understand divide-and-conquer. Mention it as a follow-up — Cisco interviewers love seeing the algorithmic variety.

Cisco-specific tips

Cisco interviewers grade this on whether you name Kadane's by name. State the invariant out loud: 'I maintain `cur` = best subarray sum ending at this index. At each step I decide whether to extend the previous subarray (cur + nums[i]) or start fresh at nums[i]. That decision is the entire algorithm.' Then write three lines. Be ready to extend to 'return the SUBARRAY itself, not just the sum' as a follow-up — track start/end indices alongside the running max.

Common mistakes

Initializing `cur` and `best` to 0 — fails on all-negative inputs because the answer might be negative.
Using `Math.max(0, cur + nums[i])` instead of `Math.max(nums[i], cur + nums[i])` — wrong for all-negative arrays.
Returning `cur` at the end instead of `best` — `cur` is the running window, `best` is the max we've ever seen.

Follow-up questions

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

Return the subarray itself, not just the sum. (Track start/end during the scan.)
Maximum Product Subarray (LC 152) — track both max and MIN because negative * negative can become max.
Maximum Subarray Sum Circular (LC 918) — wrap-around variant; total - min-subarray OR plain Kadane's.
K-Concatenation Maximum Sum (LC 1191) — Kadane's on an extended array.

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] instead of 0?

Because the array can be entirely negative. If you initialize `best` to 0, you'd return 0 on input [-3, -1, -2], but the correct answer is -1 (the single largest element). Always initialize to `nums[0]`.

Is Kadane's a 'DP' algorithm?

Yes — it's the textbook example of bottom-up DP with O(1) space. The DP table would be `cur[i] = max subarray ending at i`; the recurrence is `cur[i] = max(nums[i], cur[i-1] + nums[i])`. Since each `cur[i]` only depends on `cur[i-1]`, you collapse the array to a single variable.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →