Skip to main content

7. Maximum Subarray

easyAsked at Wix

Find the contiguous subarray with maximum sum (Kadane); Wix uses it to detect peak-traffic windows in published-site analytics.

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

Problem

Given an integer array nums, find the contiguous subarray (containing at least one number) which has 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

Example 2

Input
nums=[1]
Output
1

Approaches

1. Brute force

Check every subarray sum.

Time
O(n^2)
Space
O(1)
let max=-Infinity; for(let i=0;i<n;i++){let s=0; for(let j=i;j<n;j++){s+=nums[j]; max=Math.max(max,s)}} return max;

Tradeoff:

2. Kadane

Keep running sum, reset when negative.

Time
O(n)
Space
O(1)
function maxSubArray(nums){
  let best=nums[0],cur=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:

Wix-specific tips

Wix appreciates one extra sentence on how to extend Kadane to also return the start/end indices, since that's what their analytics dashboards actually plot.

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 Wix interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →