53. Maximum Subarray
easyAsked at BroadcomFind 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 Sam K., 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
nums = [-2,1,-3,4,-1,2,1,-5,4]6Explanation: The subarray [4,-1,2,1] has the largest sum = 6.
Example 2
nums = [1]1Explanation: Single element is the subarray.
Example 3
nums = [5,4,-1,7,8]23Explanation: 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.
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.