7. Maximum Subarray
easyAsked at CircleCIFind the contiguous subarray with the largest sum.
By Sam K., 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
6Example 2
Input
nums = [5,4,-1,7,8]Output
23Approaches
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.