5. Maximum Subarray
easyAsked at ByteDanceMaximum Subarray asks for the largest sum any contiguous slice of an integer array can reach — the home of Kadane's algorithm and one of the most-asked questions in screening rounds anywhere. ByteDance candidates report the bar is not finding Kadane's (most prepared candidates do) but explaining the one-line decision it makes at every index: extend the running subarray, or abandon it and restart — and proving why a negative running sum can never help any future window.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in ByteDance loops.
- LeetCode (2026)— Problem #53 'Maximum Subarray' — canonical statement and constraints; perennially among the top-asked array questions site-wide.
- Google Search Console (InterviewChamp) (2026-Q2)— Live search-demand data shows candidates searching this problem paired with ByteDance interview prep.
Problem
Given an integer array nums, find the contiguous subarray with the largest sum and return that sum. The array contains at least one element and may include negative numbers — including the all-negative case, where the answer is the single largest element rather than an empty window.
Constraints
1 <= nums.length <= 10^5-10^4 <= nums[i] <= 10^4The subarray must be non-empty — all-negative inputs return the maximum single element, not zero.
Examples
Example 1
nums = [-2,1,-3,4,-1,2,1,-5,4]6Explanation: The winning window is [4,-1,2,1] with sum 6. Kadane's keeps the window through the -1 dip because the running sum stays positive, then refuses to carry the -5.
Example 2
nums = [1]1Explanation: A single element is its own best subarray — the initialization case every off-by-one bug hides in.
Approaches
1. Brute force
Sum every subarray and track the max.
- Time
- O(n^2)
- Space
- O(1)
let best = -Infinity;
for (let i=0;i<n;i++){let s=0;for (let j=i;j<n;j++){s+=nums[j];best=Math.max(best,s);}}Tradeoff: Quadratic — at n = 100,000 that is ~5 billion additions, far past any judge limit. Name it in one sentence as the baseline, then derive Kadane's; lingering here on an easy-rated question costs you the round's pacing.
2. Kadane's algorithm
At each index decide whether to extend the previous subarray or start fresh. Track the running max throughout.
- Time
- O(n)
- Space
- O(1)
function maxSubArray(nums) {
let cur = nums[0], 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: Linear, constant space, two variables — optimal. The interview value is the invariant: cur is the best sum of any subarray ENDING here, and a negative cur is dead weight no future window wants. Saying that sentence is worth more than the code itself.
ByteDance-specific tips
ByteDance candidates report this in first-round screens with the follow-ups carrying the real weight: return the indices of the winning window (track a start pointer when you restart), explain the dynamic-programming reading (cur is the optimal solution to the prefix subproblem), and connect it to signal smoothing — keep accumulating a window while the aggregate is net positive, reset when accumulated noise outweighs it, the same shape a feed-ranking pipeline uses on engagement deltas. Initialize both variables to nums[0], never to 0, or all-negative arrays break.
Common mistakes
- Initializing cur and best to 0 instead of nums[0] — all-negative arrays then return 0, which is not a valid non-empty subarray sum.
- Tracking only the global max without the 'best ending here' variable — the two-variable structure IS the algorithm.
- Resetting cur to 0 instead of to nums[i] when restarting — those differ exactly when nums[i] is negative.
- Failing the 'return the actual subarray' follow-up because no start index was tracked at each restart.
Follow-up questions
An interviewer at ByteDance may pivot to one of these next:
- Maximum Product Subarray (LC 152): negatives flip sign, so you must carry BOTH a running max and a running min.
- Maximum Sum Circular Subarray (LC 918): the wrap-around case — total sum minus the minimum subarray, with the all-negative edge case.
- Divide-and-conquer version of this problem in O(n log n) — asked when interviewers probe whether you know more than one derivation.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why is abandoning a negative running sum always safe?
Any future subarray that included the negative prefix would score strictly higher without it — a prefix with negative sum can only subtract from what follows. That exchange argument is the entire correctness proof of Kadane's.
Is Kadane's algorithm dynamic programming?
Yes — cur is dp[i], the maximum sum of a subarray ending at index i, with dp[i] = max(nums[i], dp[i-1] + nums[i]). Kadane's just collapses the dp array into one variable because only dp[i-1] is ever needed.
How do I return the subarray itself, not just the sum?
Record a candidate start index whenever cur restarts at nums[i]; when best updates, freeze [start, i] as the answer window. Same complexity, two extra integers.