Skip to main content

5. Maximum Subarray

easyAsked at ByteDance

Return the largest sum of a contiguous subarray — ByteDance asks this to confirm you reach Kadane's algorithm before tracing why it generalizes to engagement-score smoothing.

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

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.

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

Example 2

Input
nums = [1]
Output
1

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:

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:

ByteDance-specific tips

ByteDance interviewers like candidates who connect Kadane's decision to ranking pipelines — keep the running window if signal is positive, reset when noise dominates.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →