Skip to main content

7. Maximum Subarray

easyAsked at CircleCI

Find the contiguous subarray with the largest sum.

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

Problem

Given an integer array nums, find the contiguous subarray with the largest sum and return its sum. The array may contain negative numbers and must contain at least one element.

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 = [5,4,-1,7,8]
Output
23

Approaches

1. Brute force

Try every (i, j) and sum the subarray.

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

Tradeoff:

2. Kadane's algorithm

Carry a running sum; reset when it goes negative. Track the best seen.

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:

CircleCI-specific tips

CircleCI applies Kadane-style scans to detect spike windows in build-duration telemetry — name the running-sum invariant out loud.

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

Practice these live with InterviewChamp.AI →