Find Maximum Subarray Divide and Conquer in DSA C++

Mental Model

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

Analogy: Imagine you have a long road with some good and bad spots. You want to find the best continuous stretch. You look at the left half, the right half, and the middle area where they meet, then choose the best stretch overall.

Array: [ -2, 1, -3, 4, -1, 2, 1, -5, 4 ]
Split: [ -2, 1, -3, 4, -1 ] | [ 2, 1, -5, 4 ]
Left max subarray -> somewhere here
Right max subarray -> somewhere here
Crossing max subarray -> crosses middle
Result: 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 continuous subarray using divide and conquer

Step 1: Split 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: Divide problem into smaller parts to solve recursively

Step 2: Find max subarray in left half recursively

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

Why: Find best subarray in left half

Step 3: Find max subarray in right half recursively

Right max subarray: [4] with sum 4

Why: Find best subarray in right half

Step 4: Find max crossing subarray crossing middle between left and right

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

Why: Check subarrays crossing the middle for max sum

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

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

Why: Final answer is the maximum among left, right, and crossing

Result:

Max subarray: 4 -> -1 -> 2 -> 1 -> null with sum 6

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

struct Result {
    int left, right, sum;
};

// Find max crossing subarray sum
Result maxCrossingSubarray(const vector<int>& arr, int left, int mid, int right) {
    int left_sum = INT_MIN, sum = 0, max_left = mid;
    for (int i = mid; i >= left; i--) {
        sum += arr[i];
        if (sum > left_sum) {
            left_sum = sum;
            max_left = i;
        }
    }
    int right_sum = INT_MIN;
    sum = 0;
    int max_right = mid + 1;
    for (int j = mid + 1; j <= right; j++) {
        sum += arr[j];
        if (sum > right_sum) {
            right_sum = sum;
            max_right = j;
        }
    }
    return {max_left, max_right, left_sum + right_sum};
}

// Recursive divide and conquer function
Result maxSubarrayDC(const vector<int>& arr, int left, int right) {
    if (left == right) {
        return {left, right, arr[left]};
    }
    int mid = (left + right) / 2;
    Result left_res = maxSubarrayDC(arr, left, mid);
    Result right_res = maxSubarrayDC(arr, mid + 1, right);
    Result cross_res = maxCrossingSubarray(arr, left, mid, right);

    if (left_res.sum >= right_res.sum && left_res.sum >= cross_res.sum) {
        return left_res;
    } else if (right_res.sum >= left_res.sum && right_res.sum >= cross_res.sum) {
        return right_res;
    } else {
        return cross_res;
    }
}

int main() {
    vector<int> arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    Result res = maxSubarrayDC(arr, 0, arr.size() - 1);
    cout << "Max subarray sum: " << res.sum << "\n";
    cout << "Subarray elements: ";
    for (int i = res.left; i <= res.right; i++) {
        cout << arr[i];
        if (i < res.right) cout << " -> ";
    }
    cout << " -> null" << endl;
    return 0;
}

for (int i = mid; i >= left; i--) { sum += arr[i]; if (sum > left_sum) { left_sum = sum; max_left = i; } }

Find max sum subarray ending at mid going left

for (int j = mid + 1; j <= right; j++) { sum += arr[j]; if (sum > right_sum) { right_sum = sum; max_right = j; } }

Find max sum subarray starting at mid+1 going right

if (left_res.sum >= right_res.sum && left_res.sum >= cross_res.sum) return left_res;

Choose max subarray among left, right, crossing

else if (right_res.sum >= left_res.sum && right_res.sum >= cross_res.sum) return right_res;

Choose max subarray among left, right, crossing

else return cross_res;

Choose max subarray among left, right, crossing

Output

Max subarray sum: 6

Subarray elements: 4 -> -1 -> 2 -> 1 -> null

Complexity Analysis

Time: O(n log n) because the array is split 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 which checks all subarrays; slower than Kadane's O(n) but uses divide and conquer strategy

Edge Cases

Array with single element

Returns that element as max subarray

DSA C++

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

Array with all negative numbers

Returns the largest (least negative) single element

DSA C++

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

Array with all positive numbers

Returns the entire array as max subarray

DSA C++

maxCrossingSubarray sums all positive elements crossing mid

When to Use This Pattern

When asked to find maximum sum of a continuous subarray and recursion or divide and conquer is allowed, use this pattern to split and combine results efficiently.

Common Mistakes

Mistake: Not correctly handling the crossing subarray that spans both halves
Fix: Implement a function to find max crossing subarray by expanding from middle to left and right

Mistake: Returning incorrect indices or sums when comparing left, right, and crossing results
Fix: Compare sums carefully and return the corresponding subarray indices and sum

Summary

Finds the maximum sum continuous subarray using divide and conquer.

Use when you want a recursive approach splitting the problem into halves.

The key insight is to consider max subarrays in left, right, and crossing the middle.

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 max subarray sum

C. Divide 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 max sum

Solution

1. Step 1: Understand divide and conquer strategy

   The array is split 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:

   Divide the array into two halves, find max subarray in left, right, and crossing middle, then combine results -> Option C

4. Quick Check:

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

Hint: Split array, check left, right, and crossing sums [OK]

Common Mistakes:

• Thinking sorting helps find max subarray sum
• Ignoring subarrays crossing the middle
• Trying to check all subarrays without divide and conquer

2. Which of the following is the correct base case condition in the divide and conquer function for maximum subarray?

easy

A. if (low >= high) return arr[low] + arr[high];

B. if (low > high) return 0;

C. if (low == high) return 0;

D. if (low == high) return arr[low];

Solution

1. Step 1: Identify base case for single element

   When low equals high, the subarray has one element, so max sum is that element itself.

2. Step 2: Check options for correct base case

   if (low == high) return arr[low]; returns arr[low] when low == high, which is correct base case.

3. Final Answer:

   if (low == high) return arr[low]; -> Option D

4. Quick Check:

   Single element subarray max sum = element value [OK]

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

Common Mistakes:

• Returning 0 for single element subarray
• Using incorrect comparison operators in base case
• Returning sum of two elements when only one element left

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

int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
int n = 9;
int maxCrossingSum(int arr[], int low, int mid, int high) {
    int sum = 0, left_sum = INT_MIN;
    for (int i = mid; i >= low; i--) {
        sum += arr[i];
        if (sum > left_sum) left_sum = sum;
    }
    sum = 0; int right_sum = INT_MIN;
    for (int i = mid + 1; i <= high; i++) {
        sum += arr[i];
        if (sum > right_sum) right_sum = sum;
    }
    return left_sum + right_sum;
}
int maxSubArraySum(int arr[], int low, int high) {
    if (low == high) return arr[low];
    int mid = (low + high) / 2;
    int left_max = maxSubArraySum(arr, low, mid);
    int right_max = maxSubArraySum(arr, mid + 1, high);
    int cross_max = maxCrossingSum(arr, low, mid, high);
    return max(max(left_max, right_max), cross_max);
}
int result = maxSubArraySum(arr, 0, n - 1);
std::cout << result;

medium

A. 6

B. 7

C. 5

D. 4

Solution

1. Step 1: Identify the maximum subarray

   The array is [-2, 1, -3, 4, -1, 2, 1, -5, 4]. The subarray [4, -1, 2, 1] (indices 3-6) sums to 6, the maximum.

2. Step 2: Verify code execution

   Top-level split: left_max=4, right_max=4, cross_max=6 (left suffix 4 + right prefix -1+2+1=2). Returns 6.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Max subarray sum = 6 [OK]

Hint: Check sums of subarrays crossing middle carefully [OK]

Common Mistakes:

• Confusing max crossing sum with max overall sum
• Miscounting indices in loops
• Assuming max sum includes all positive numbers only

4. Identify the bug in this divide and conquer max subarray code snippet:

int maxCrossingSum(int arr[], int low, int mid, int high) {
    int sum = 0, left_sum = 0;
    for (int i = mid; i >= low; i--) {
        sum += arr[i];
        if (sum > left_sum) left_sum = sum;
    }
    sum = 0; int right_sum = 0;
    for (int i = mid + 1; i <= high; i++) {
        sum += arr[i];
        if (sum > right_sum) right_sum = sum;
    }
    return left_sum + right_sum;
}

medium

A. left_sum and right_sum should be initialized to INT_MIN, not 0

B. The loops should run from low to mid and mid+1 to high respectively

C. sum should not be reset to 0 before right loop

D. The function should return max(left_sum, right_sum) instead of sum

Solution

1. Step 1: Check initialization of left_sum and right_sum

   They are initialized to 0, which fails if all numbers are negative because max sum could be less than 0.

2. Step 2: Correct initialization to INT_MIN

   Initializing left_sum and right_sum to INT_MIN ensures negative sums are correctly handled.

3. Final Answer:

   left_sum and right_sum should be initialized to INT_MIN, not 0 -> Option A

4. Quick Check:

   Initialize max sums to INT_MIN to handle negatives [OK]

Hint: Use INT_MIN for max sums to handle negative values [OK]

Common Mistakes:

• Initializing max sums to zero causing wrong results
• Incorrect loop directions
• Not resetting sum before right loop

5. Given an array arr = [-1, -2, -3, -4], what will the divide and conquer maximum subarray function return?

hard

A. -10

B. -1

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 element (least negative).

2. Step 2: Find largest element in arr

   Elements are -1, -2, -3, -4. The largest is -1.

3. Final Answer:

   -1 -> Option B

4. Quick Check:

   Max subarray in negatives = max element [OK]

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

Common Mistakes:

• Returning sum of all elements instead of max single element
• Returning zero incorrectly assuming empty subarray
• Ignoring negative values in max calculation