LeetCode 53. Maximum Subarray - divide and conquer approach

Link to LeetCode 53. Maximum Subarray problem.

Previously I've wrote how to optimize a brute-force solution from O(n2) time complexity to O(n) time complexity and O(1) space complexity. But the problem also included a follow-up challenge:

Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

Let's solve this problem step by step using the Divide and Conquer approach.

Core idea of Divide and Conquer approach

The Divide and Conquer approach consists of three steps:

• Divide - split the array into two halves.
• Conquer - recursively find the maximum subarray sum in each half.
• Combine - find the maximum subarray sum that crosses the midpoint.

Why do we need to check three cases? Any contiguous subarray must fall into one of three categories relative to the midpoint (three possible locations of the maximum subarray):

• Entirely in the left half
• Entirely in the right half
• Crossing the midpoint

By checking all three cases, we guarantee that we find the maximum subarray sum.

Let's walk through the Java solution step by step.

class Solution {
    public int maxSubArray(int[] nums) {
        // Process the entire array, from index 0 to n - 1.
        return divide(nums, 0, nums.length - 1);
    }

    // Find the maximum subarray sum within [left, right].
    private int divide(int[] nums, int left, int right) {
        // Base case: the segment contains only one element.
        if (left == right) {
            return nums[left];
        }
        // Find the middle index without overflowing the sum.
        int mid = left + (right - left) / 2;
        // Recursively find the best subarray in the left half.
        int leftMax = divide(nums, left, mid);
        // Recursively find the best subarray in the right half.
        int rightMax = divide(nums, mid + 1, right);
        // Find the best subarray crossing the middle.
        int crossMax = crossingSum(nums, left, mid, right);
        // Return the maximum of the three possible cases.
        return Math.max(Math.max(leftMax, rightMax), crossMax);
    }

    // Find the maximum sum of a subarray crossing the middle.
    private int crossingSum(int[] nums, int left, int mid, int right) {
        // Store the running sum while scanning the left half.
        int sum = 0;
        // Store the maximum suffix sum of the left half.
        int leftSum = Integer.MIN_VALUE;
        for (int i = mid; i >= left; i--) {
            sum += nums[i];
            // Update the best suffix sum found so far.
            leftSum = Math.max(leftSum, sum);
        }
        // Reset the running sum for the right half.
        sum = 0;
        // Store the maximum prefix sum of the right half.
        int rightSum = Integer.MIN_VALUE;
        for (int i = mid + 1; i <= right; i++) {
            // Include the current element in the running sum.
            sum += nums[i];
            // Update the best prefix sum found so far.
            rightSum = Math.max(rightSum, sum);
        }
        // Combine both sums into one crossing subarray.
        return leftSum + rightSum;
    }
}

Key points

Base case

if (left == right) {
    return nums[left];
}

This is the base case of the recursion. When left == right, the current segment contains a single element. We return nums[left] instead of 0 because the problem requires the subarray to be non-empty.

Splitting the array

int mid = left + (right - left) / 2;

instead of:

int mid = (left + right) / 2;

Both approaches are mathematically equivalent, but left + right can theoretically cause integer overflow for large indices. The first approach left + (right - left) / 2 avoids this risk for valid, non-negative array indices.

Find the maximum suffix of the left half

int sum = 0;
int leftSum = Integer.MIN_VALUE;
for (int i = mid; i >= left; i--) {
    sum += nums[i];
    leftSum = Math.max(leftSum, sum);
}

We iterate from mid to left, rather than the other way around, because a subarray that crosses the midpoint must include nums[mid]. Since the subarray must be contiguous, its left portion must end at mid.

Find the maximum prefix of the right part

sum = 0;
int rightSum = Integer.MIN_VALUE;
for (int i = mid + 1; i <= right; i++) {
    sum += nums[i];
    rightSum = Math.max(rightSum, sum);
}

Here, we move from left to right because the subarray that crosses the midpoint must include nums[mid + 1].

Complexity

Time complexity: O(log n)

At each level of recursion:

• The array is divided approximately in half.
• Two recursive calls are made.

crossingSum examines all elements of the current segment in O(n) time.

Each level performs O(n) work. The number of levels is O(log n) because the segment size is approximately halved at each step.

Space complexity: O(log n)

We do not create any additional arrays. All calculations are performed directly on the original nums array using indices. However, recursive calls use the call stack. Since each recursive call divides the segment approximately in half, the maximum recursion depth is O(log n). Each level stores only a constant number of local variables.

Important: Although each call makes two recursive calls, they are executed sequentially. Their call stacks do not accumulate simultaneously to O(n).

Why is Divide and Conquer slower than Kadane's algorithm?

Kadane's algorithm processes each element only once. Divide and Conquer repeatedly processes elements at different levels of recursion when calculating crossingSum.

Help me create more content