⚠️ This visualization was AI-generated and may contain inaccuracies. Please verify against the original LeetCode problem (#53) before relying on it.

Maximum Subarray (Divide & Conquer)

An interactive visualization of the divide and conquer approach for finding the contiguous subarray with the largest sum. Watch how the array is split, and how left, right, and crossing subarrays are compared at each recursion level.

Divide and Conquer LeetCode 53 ↗ Medium

The Problem

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

A subarray is a contiguous part of an array. For example, given [-2, 1, -3, 4, -1, 2, 1, -5, 4], the contiguous subarray [4, -1, 2, 1] has the largest sum = 6.

Interactive Visualization

Array (comma-separated)

Preset

Speed:

Array Visualization

Code

fun maxSubArray(nums: IntArray, left: Int, right: Int): Int {    if (left == right) {        return nums[left]    }    val mid = (left + right) / 2    val leftMax = maxSubArray(nums, left, mid)    val rightMax = maxSubArray(nums, mid + 1, right)    val crossMax = maxCrossing(nums, left, mid, right)    return maxOf(leftMax, rightMax, crossMax)}fun maxCrossing(nums: IntArray, left: Int, mid: Int, right: Int): Int {    var leftSum = Int.MIN_VALUE    var currSum = 0    for (i in mid downTo left) {        currSum += nums[i]        leftSum = maxOf(leftSum, currSum)    }    var rightSum = Int.MIN_VALUE    currSum = 0    for (i in mid + 1..right) {        currSum += nums[i]        rightSum = maxOf(rightSum, currSum)    }    return leftSum + rightSum}

def maxSubArray(nums, left, right):    if left == right:        return nums[left]    mid = (left + right) // 2    left_max = maxSubArray(nums, left, mid)    right_max = maxSubArray(nums, mid + 1, right)    cross_max = maxCrossing(nums, left, mid, right)    return max(left_max, right_max, cross_max)def maxCrossing(nums, left, mid, right):    left_sum = float('-inf')    curr_sum = 0    for i in range(mid, left - 1, -1):        curr_sum += nums[i]        left_sum = max(left_sum, curr_sum)    right_sum = float('-inf')    curr_sum = 0    for i in range(mid + 1, right + 1):        curr_sum += nums[i]        right_sum = max(right_sum, curr_sum)    return left_sum + right_sum

Status

Press Step or Play to begin.

How It Works

Key Insight

The maximum subarray must lie in exactly one of three places relative to the midpoint: entirely in the left half, entirely in the right half, or crossing the midpoint. By recursively solving the left and right halves, and computing the best crossing subarray, we compare all three candidates and return the maximum.

The Algorithm

Base case: If left == right, the subarray is a single element — return it.
Divide: Compute mid = (left + right) // 2 and recursively find the max subarray in nums[left..mid] and nums[mid+1..right].
Crossing subarray: Expand left from mid toward left, tracking the best sum. Then expand right from mid+1 toward right, tracking the best sum. The crossing max is the sum of these two best halves.
Conquer: Return max(left_max, right_max, cross_max).

Complexity

Time O(n log n)

Space O(log n)

At each of the O(log n) recursion levels, we do O(n) total work computing crossing subarrays, giving O(n log n) overall. The recursion stack uses O(log n) space.