1. Base case
A single element is its own best subarray.
if (left === right) return nums[left]Typorithm · medium
Max Subarray (D&C)
▷ Interactive algorithm labmax-subarray-divide-conquerdivide-and-conquercrossing-sumcombine-stepmidpoint
Saved on this device
Full lesson · 8 learning steps Open any exercise for focused practice
10%
Step 1 of 8 · intro card
Learn Max Subarray (D&C)
Divide & Conquer
Split at the middle; the best subarray is the largest of the left half, the right half, or one that crosses the midline.
The maximum subarray either lies entirely in the left half, entirely in the right half, or straddles the midpoint.
The left and right cases are solved by recursion; the crossing case is the combine step.
To build the crossing sum, extend left from mid to find the best prefix ending at mid, extend right from mid+1 to find the best suffix starting there, then add them.
Preparing algorithm lab…
01
Three candidates: left, right, crossing.
02
Crossing must include mid and mid+1.
03
O(n log n) — log n levels, O(n) crossing scan.
function maxSubarray(nums, left = 0, right = nums.length - 1) {
if (left === right) return nums[left];
const mid = Math.floor((left + right) / 2);
const leftBest = maxSubarray(nums, left, mid);
const rightBest = maxSubarray(nums, mid + 1, right);
let leftSum = -Infinity;
let sum = 0;
for (let i = mid; i >= left; i -= 1) {
sum += nums[i];
leftSum = Math.max(leftSum, sum);
}
let rightSum = -Infinity;
sum = 0;
for (let i = mid + 1; i <= right; i += 1) {
sum += nums[i];
rightSum = Math.max(rightSum, sum);
}
const crossBest = leftSum + rightSum;
return Math.max(leftBest, rightBest, crossBest);
}Read the implementation
Connect each part of the code to the concept before you type.
2. Divide at middle
Split the range in half to recurse on each side.
const mid = Math.floor((left + right) / 2)3. Conquer halves
Solve the left and right halves independently.
const rightBest = maxSubarray(nums, mid + 1, right)4. Extend left from mid
Walk left from mid, tracking the best prefix that ends at mid.
for (let i = mid; i >= left; i -= 1)5. Crossing sum
The best crossing subarray joins the best left half ending at mid with the best right half starting at mid+1.
const crossBest = leftSum + rightSum6. Combine
The answer is the largest of left, right, and crossing results.
return Math.max(leftBest, rightBest, crossBest)A complete learning loop
01
Understand
Read the concept map and follow the code breakdown.
02
Reconstruct
Type the implementation, repair mistakes and work through every recall exercise.
03
Verify
Use the final check without hints; revisit weak concepts in short practice sessions.