Skip to main content

53. Maximum Subarray

easyAsked at Broadcom

Find the contiguous subarray with the largest sum. Broadcom asks Kadane's algorithm to verify that candidates understand linear-scan optimisation — directly applicable to signal-burst detection in network traffic analysis and time-series monitoring of chip telemetry.

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

Source citations

Public interview reports confirming this problem appears in Broadcom loops.

  • Glassdoor (2026-Q1)— Reported in Broadcom SWE interview summaries as a Kadane's algorithm problem in early coding rounds.
  • Blind (2025-10)— Broadcom threads cite Maximum Subarray as a frequent warm-up checking DP intuition.

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 is the subarray.

Example 3

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

Explanation: The entire array is the maximum subarray.

Approaches

1. Brute force (O(n²))

Try every starting index and extend the subarray, tracking the running sum and global maximum.

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

Tradeoff: O(n²) — only mention as the starting point before presenting Kadane's.

2. Kadane's algorithm

At each index, either extend the current subarray or start a new one (take the element alone). The decision is: currentSum = max(nums[i], currentSum + nums[i]).

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

Tradeoff: O(n) time, O(1) space. Kadane's is the canonical answer and should be delivered first. The key insight — reset the window when the running sum goes negative — is the same logic used to detect throughput-collapse windows in network monitoring.

Broadcom-specific tips

At Broadcom, name the algorithm: 'This is Kadane's algorithm.' Explain the intuition in one sentence: 'If the running sum becomes negative, it only drags down any future subarray, so I reset to the current element.' Follow-up questions often involve returning the actual subarray indices, not just the sum — track start and end pointers as an extension.

Common mistakes

  • Initialising maxSum to 0 instead of nums[0] — fails when all elements are negative.
  • Not handling the single-element array before the loop.
  • Confusing 'current sum' with 'global max' — update both but return only the global max.
  • Using an O(n) prefix-sum array when O(1) space suffices.

Follow-up questions

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

  • Return the actual subarray indices (not just the sum).
  • Maximum subarray in a circular array (LC 918).
  • Maximum product subarray (LC 152) — the reset logic changes because negatives can flip sign.

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 work?

A negative running sum can only harm any future subarray. Resetting to the current element is equivalent to starting a fresh window — the global max captures the best window seen so far.

What if the array contains all negative numbers?

Initialising both currentSum and maxSum to nums[0] handles this correctly — the answer is the least-negative element.

How do I track the subarray bounds?

Keep a start pointer that resets whenever you start a new window, and an end pointer that updates whenever you update maxSum. Record them alongside maxSum.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →