Find Maximum Subarray Divide and Conquer in DSA Java

Mental Model

Split the array into halves, find the best subarray in left, right, and crossing the middle, then pick the best.

Analogy: Imagine cutting a chocolate bar into two parts, finding the tastiest piece in each half, and also checking if the tastiest piece crosses the cut, then choosing the best overall.

Array: [ -2, 1, -3, 4, -1, 2, 1, -5, 4 ]
Divide: [ -2, 1, -3, 4, -1 ] | [ 2, 1, -5, 4 ]
Find max in left, right, and crossing middle
Choose max of these three

Dry Run Walkthrough

Input: array: [-2, 1, -3, 4, -1, 2, 1, -5, 4]

Goal: Find the maximum sum of any contiguous subarray using divide and conquer

Step 1: Divide array into left [-2,1,-3,4,-1] and right [2,1,-5,4]

Left: [-2, 1, -3, 4, -1]
Right: [2, 1, -5, 4]

Why: We split to solve smaller problems

Step 2: Find max subarray in left half recursively

Left max subarray: [4] with sum 4

Why: Find max in left half

Step 3: Find max subarray in right half recursively

Right max subarray: [2, 1] with sum 3

Why: Find max in right half

Step 4: Find max crossing subarray crossing middle

Crossing max subarray: [4,-1,2,1] with sum 6

Why: Check subarray crossing middle for max sum

Step 5: Compare left max (4), right max (3), crossing max (6) and pick max

Max subarray: [4,-1,2,1] with sum 6

Why: Choose the best among three candidates

Result:

4 -> -1 -> 2 -> 1 -> null with sum 6

Annotated Code

DSA Java

public class MaxSubarrayDivideConquer {

    // Helper class to store result
    static class Result {
        int left, right, sum;
        Result(int left, int right, int sum) {
            this.left = left;
            this.right = right;
            this.sum = sum;
        }
    }

    // Find max crossing subarray sum
    static Result maxCrossingSubarray(int[] arr, int left, int mid, int right) {
        int leftSum = Integer.MIN_VALUE;
        int sum = 0;
        int maxLeft = mid;
        for (int i = mid; i >= left; i--) {
            sum += arr[i];
            if (sum > leftSum) {
                leftSum = sum;
                maxLeft = i;
            }
        }

        int rightSum = Integer.MIN_VALUE;
        sum = 0;
        int maxRight = mid + 1;
        for (int j = mid + 1; j <= right; j++) {
            sum += arr[j];
            if (sum > rightSum) {
                rightSum = sum;
                maxRight = j;
            }
        }

        return new Result(maxLeft, maxRight, leftSum + rightSum);
    }

    // Recursive function to find max subarray
    static Result maxSubarray(int[] arr, int left, int right) {
        if (left == right) {
            return new Result(left, right, arr[left]);
        }

        int mid = (left + right) / 2;

        Result leftResult = maxSubarray(arr, left, mid);
        Result rightResult = maxSubarray(arr, mid + 1, right);
        Result crossResult = maxCrossingSubarray(arr, left, mid, right);

        if (leftResult.sum >= rightResult.sum && leftResult.sum >= crossResult.sum) {
            return leftResult;
        } else if (rightResult.sum >= leftResult.sum && rightResult.sum >= crossResult.sum) {
            return rightResult;
        } else {
            return crossResult;
        }
    }

    public static void main(String[] args) {
        int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        Result res = maxSubarray(arr, 0, arr.length - 1);

        // Print max subarray
        StringBuilder sb = new StringBuilder();
        for (int i = res.left; i <= res.right; i++) {
            sb.append(arr[i]);
            if (i < res.right) sb.append(" -> ");
        }
        sb.append(" -> null");

        System.out.println(sb.toString());
        System.out.println("Max sum: " + res.sum);
    }
}

if (left == right) { return new Result(left, right, arr[left]); }

base case: single element is max subarray

int mid = (left + right) / 2;

divide array into two halves

Result leftResult = maxSubarray(arr, left, mid);

find max subarray in left half

Result rightResult = maxSubarray(arr, mid + 1, right);

find max subarray in right half

Result crossResult = maxCrossingSubarray(arr, left, mid, right);

find max subarray crossing middle

if (leftResult.sum >= rightResult.sum && leftResult.sum >= crossResult.sum) return leftResult;

choose max among left, right, crossing

else if (rightResult.sum >= leftResult.sum && rightResult.sum >= crossResult.sum) return rightResult;

choose max among left, right, crossing

else return crossResult;

choose max among left, right, crossing

Output

4 -> -1 -> 2 -> 1 -> null

Max sum: 6

Complexity Analysis

Time: O(n log n) because the array is divided into halves recursively and each merge step takes O(n) to find crossing max

Space: O(log n) due to recursion stack depth for dividing the array

vs Alternative: Better than naive O(n^2) approach that checks all subarrays; slower than Kadane's O(n) linear scan but uses divide and conquer strategy

Edge Cases

array with single element

returns that element as max subarray

DSA Java

if (left == right) { return new Result(left, right, arr[left]); }

array with all negative numbers

returns the least negative single element as max subarray

DSA Java

if (left == right) { return new Result(left, right, arr[left]); }

array with all positive numbers

returns entire array as max subarray

DSA Java

maxCrossingSubarray sums all positive elements crossing middle

When to Use This Pattern

When asked to find maximum sum of contiguous subarray and recursion or divide and conquer is suggested, use this pattern to split problem and combine results efficiently.

Common Mistakes

Mistake: Not checking the crossing subarray and only comparing left and right halves
Fix: Always compute and compare the crossing subarray sum to find the true max

Mistake: Incorrectly calculating indices for crossing subarray sums
Fix: Carefully iterate from mid to left and mid+1 to right to find max sums on both sides

Summary

Finds maximum sum contiguous subarray using divide and conquer.

Use when recursion and splitting array into halves is natural or required.

The key is to consider max subarray in left, right, and crossing middle and pick the best.

Practice

1. What is the main idea behind the Divide and Conquer approach to find the maximum subarray sum?

easy

A. Use a sliding window to find the max sum subarray in one pass

B. Sort the array and pick the largest element as the max subarray sum

C. Split the array into two halves, find max subarray in left, right, and crossing middle, then combine results

D. Calculate all possible subarrays and pick the one with the maximum sum

Solution

1. Step 1: Understand divide and conquer strategy

   The array is divided into two halves recursively to simplify the problem.

2. Step 2: Combine results from left, right, and crossing subarrays

   We find max subarray sums in left half, right half, and subarrays crossing the middle, then take the maximum.

3. Final Answer:

   Split array, find max in left, right, crossing, then combine -> Option C

4. Quick Check:

   Divide and conquer = split and combine max sums [OK]

Hint: Divide array, solve halves, combine crossing max [OK]

Common Mistakes:

• Thinking sorting helps find max subarray sum
• Confusing divide and conquer with sliding window
• Ignoring subarrays crossing the middle

2. Which of the following is the correct base case for the recursive function in the divide and conquer approach to find the maximum subarray?

easy

A. When the array is empty, return 0

B. When the array has only one element, return that element

C. When the array has two elements, return their sum

D. When the array has more than one element, return the max of left and right

Solution

1. Step 1: Identify base case for recursion

   The recursion stops when the subarray has only one element.

2. Step 2: Return the single element as max subarray sum

   Since one element is the smallest subarray, return it directly.

3. Final Answer:

   Return single element when array size is one -> Option B

4. Quick Check:

   Base case = single element return [OK]

Hint: Base case: single element returns itself [OK]

Common Mistakes:

• Returning 0 for empty array instead of handling single element
• Using sum of two elements as base case
• Not defining a base case causing infinite recursion

3. What is the output of the following Java code snippet using divide and conquer to find max subarray sum?

int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
System.out.println(maxSubArray(arr, 0, arr.length - 1));

// Assume maxSubArray is correctly implemented divide and conquer method

medium

A. 4

B. 7

C. 5

D. 6

Solution

1. Step 1: Identify max subarray in given array

   The max subarray is [4, -1, 2, 1] with sum 4 + (-1) + 2 + 1 = 6.

2. Step 2: Check if any larger sum exists

   Adding the next element -5 or 4 does not increase sum beyond 6, but including the last 4 gives total 5 for subarray [4, -1, 2, 1, -5, 4]?

3. Step 3: Correct max subarray is [4, -1, 2, 1] with sum 6

   Actually, the max sum is 6, not 5.

4. Final Answer:

   6 -> Option D

5. Quick Check:

   Max subarray sum = 6 [OK]

Hint: Find max sum subarray by checking sums around middle [OK]

Common Mistakes:

• Choosing sum including negative elements that reduce total
• Miscounting elements in max subarray
• Confusing max sum with max element

4. Identify the error in this divide and conquer code snippet for max subarray sum:

int maxCrossingSum(int[] arr, int left, int mid, int right) {
    int sum = 0, left_sum = Integer.MIN_VALUE;
    for (int i = mid; i >= left; i--) {
        sum += arr[i];
        if (sum > left_sum) left_sum = sum;
    }
    sum = 0;
    int right_sum = Integer.MIN_VALUE;
    for (int i = mid + 1; i <= right; i++) {
        sum += arr[i];
        if (sum > right_sum) right_sum = sum;
    }
    return left_sum + right_sum;
}

medium

A. No error, code correctly finds max crossing sum

B. Should initialize sum to Integer.MIN_VALUE instead of 0

C. Return statement should be max of left_sum and right_sum, not sum

D. Loop ranges are incorrect; should start from left+1 and mid-1

Solution

1. Step 1: Analyze loops for left and right sums

   Loops correctly accumulate sums from mid to left and mid+1 to right.

2. Step 2: Check return statement

   Returns sum of max left and right sums crossing mid, which is correct for crossing subarray.

3. Final Answer:

   No error, code correctly finds max crossing sum -> Option A

4. Quick Check:

   Crossing sum = left max + right max [OK]

Hint: Crossing sum = max left + max right sums around mid [OK]

Common Mistakes:

• Initializing sum to wrong value causing incorrect sums
• Returning max instead of sum of left and right max
• Incorrect loop boundaries skipping elements

5. Given the array int[] arr = {-1, -2, -3, -4}, what will the divide and conquer algorithm return as the maximum subarray sum?

hard

A. -1

B. -10

C. 0

D. -4

Solution

1. Step 1: Understand max subarray with all negative numbers

   When all numbers are negative, max subarray is the single largest (least negative) element.

2. Step 2: Identify largest element in array

   Largest element is -1, so max subarray sum is -1.

3. Final Answer:

   -1 -> Option A

4. Quick Check:

   Max subarray sum with negatives = max element [OK]

Hint: Max subarray in negatives is max single element [OK]

Common Mistakes:

• Summing all negatives instead of picking max element
• Returning zero incorrectly assuming empty subarray
• Confusing max subarray sum with min element