Find Maximum Subarray Divide and Conquer in DSA C

Mental Model

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

Analogy: Imagine you want to find the best stretch of road with the most beautiful views on a long trip. You split the trip into two parts, find the best stretch in each part, and also check if the best stretch crosses the middle point between the two parts.

Array: [ -2, 1, -3, 4, -1, 2, 1, -5, 4 ]
Split: [ -2, 1, -3, 4 ] | [ -1, 2, 1, -5, 4 ]
Left max subarray: ?
Right max subarray: ?
Crossing max subarray: ?

Dry Run Walkthrough

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

Goal: Find the maximum sum subarray using divide and conquer

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

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

Why: Divide problem into smaller parts to solve recursively

Step 2: Find max subarray in left half by splitting again

Left split: [-2,1] and [-3,4]

Why: Keep dividing until base case of single element

Step 3: Base case: max subarray of [-2] is -2, [1] is 1

Max left-left: 1
Max left-right: max subarray of [-3,4]

Why: Single elements are base max subarrays

Step 4: Find max subarray crossing middle in left half: from 1 to 4

Crossing sum: 1 + (-3) + 4 = 2

Why: Check if crossing subarray is better than halves

Step 5: Max subarray in left half is max of left-left (1), left-right (4), crossing (2)

Left max subarray sum = 4 (subarray [4])

Why: Choose best among left parts

Step 6: Find max subarray in right half [-1,2,1,-5,4] similarly

Right max subarray sum = 4 (subarray [4])

Why: Divide and conquer on right half

Step 7: Find max crossing subarray crossing middle of whole array (between 4 and -1)

Crossing sum = max suffix left + max prefix right = (4 + -1 + 2 + 1) = 6

Why: Check subarray crossing middle for max sum

Step 8: Final max subarray is max of left max (4), right max (4), crossing max (6)

Max subarray sum = 6, subarray [4, -1, 2, 1]

Why: Combine results to get final answer

Result:

Final max subarray: 4 -> -1 -> 2 -> 1 -> null with sum 6

Annotated Code

DSA C

#include <stdio.h>
#include <limits.h>

// Function to find max crossing subarray sum
int maxCrossingSum(int arr[], int left, int mid, int right) {
    int sum = 0;
    int left_sum = INT_MIN;
    for (int i = mid; i >= left; i--) {
        sum += arr[i];
        if (sum > left_sum) {
            left_sum = sum; // update max suffix sum on left
        }
    }

    sum = 0;
    int right_sum = INT_MIN;
    for (int i = mid + 1; i <= right; i++) {
        sum += arr[i];
        if (sum > right_sum) {
            right_sum = sum; // update max prefix sum on right
        }
    }

    return left_sum + right_sum; // max crossing sum
}

// Recursive function to find max subarray sum
int maxSubArraySum(int arr[], int left, int right) {
    if (left == right) {
        return arr[left]; // base case single element
    }

    int mid = (left + right) / 2;

    int left_max = maxSubArraySum(arr, left, mid); // max in left half
    int right_max = maxSubArraySum(arr, mid + 1, right); // max in right half
    int cross_max = maxCrossingSum(arr, left, mid, right); // max crossing mid

    // return max of three
    if (left_max >= right_max && left_max >= cross_max) {
        return left_max;
    } else if (right_max >= left_max && right_max >= cross_max) {
        return right_max;
    } else {
        return cross_max;
    }
}

int main() {
    int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    int max_sum = maxSubArraySum(arr, 0, n - 1);
    printf("Maximum subarray sum is %d\n", max_sum);
    return 0;
}

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

base case: single element max subarray

int mid = (left + right) / 2;

divide array into two halves

int left_max = maxSubArraySum(arr, left, mid);

find max subarray in left half recursively

int right_max = maxSubArraySum(arr, mid + 1, right);

find max subarray in right half recursively

int cross_max = maxCrossingSum(arr, left, mid, right);

find max subarray crossing the middle

return max of left_max, right_max, cross_max;

combine results to get max subarray sum

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

find max suffix sum on left side

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

find max prefix sum on right side

Output

Maximum subarray sum is 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 sum

Space: O(log n) due to recursion stack depth proportional to log n

vs Alternative: Better than naive O(n^2) approach that 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 sum

DSA C

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

array with all negative numbers

returns the largest (least negative) single element

DSA C

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

empty array (not handled explicitly)

undefined behavior, input size must be >=1

DSA C

none (caller must ensure non-empty input)

When to Use This Pattern

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

Common Mistakes

Mistake: Not correctly calculating the crossing sum by missing max suffix or prefix sums
Fix: Calculate max suffix sum from mid to left and max prefix sum from mid+1 to right carefully

Mistake: Forgetting base case of single element leading to infinite recursion
Fix: Add base case: if left == right return arr[left]

Summary

Finds the maximum sum of any contiguous subarray using divide and conquer.

Use when you want a recursive approach splitting array into halves and combining results.

The key insight is to consider max subarray in left half, right half, 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 maximum 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 sum of all subarrays and pick the maximum

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 of these.

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, solve, combine [OK]

Hint: Split array, solve halves, check crossing sum, combine [OK]

Common Mistakes:

• Thinking sorting helps find max subarray sum
• Ignoring subarrays crossing the middle
• Trying to sum all subarrays directly

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 0;

B. if (low > high) return 0;

C. if (low < high) return arr[low] + arr[high];

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

Solution

1. Step 1: Identify base case meaning

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

2. Step 2: Match base case condition

   The condition if (low == high) return arr[low]; correctly returns the single element's value.

3. Final Answer:

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

4. Quick Check:

   Single element subarray returns element value [OK]

Hint: Base case: one element means return that element [OK]

Common Mistakes:

• Returning 0 when low == high
• Using incorrect comparison operators
• Returning sum of two elements instead of one

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

int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
int result = maxSubArray(arr, 0, 8);
printf("%d", result);

Assume maxSubArray is correctly implemented divide and conquer function.

medium

A. 6

B. 7

C. 5

D. 4

Solution

1. Step 1: Identify max subarray in given array

   The maximum subarray is [4, -1, 2, 1] with sum 4 + (-1) + 2 + 1 = 6, but check if including more elements helps.

2. Step 2: Check if extending subarray increases sum

   Including the element before 4 is -3 (reduces sum), after 1 is -5 (reduces sum), so max sum is 6.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Max subarray sum = 6 [OK]

Hint: Find max sum of continuous elements [OK]

Common Mistakes:

• Counting non-continuous elements
• Miscomputing sums with negative numbers
• Assuming max element alone is answer

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

int maxCrossingSum(int arr[], int low, int mid, int high) {
    int left_sum = 0, sum = 0;
    for (int i = mid; i >= low; i--) {
        sum += arr[i];
        if (sum > left_sum)
            left_sum = sum;
    }
    int right_sum = 0;
    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 start from low and high, not mid

C. sum variable should not be reset between loops

D. Return statement should subtract left_sum from right_sum

Solution

1. Step 1: Understand initialization of sums

   Initializing left_sum and right_sum to 0 causes errors if all numbers are negative, as max sum could be less than 0.

2. Step 2: Correct initialization

   They should be initialized to the smallest integer (INT_MIN) to correctly track max sums even if negative.

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 arrays [OK]

Common Mistakes:

• Initializing max sums to zero causes wrong results
• Not resetting sum variable properly
• Incorrect loop ranges

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

hard

A. 0 because empty subarray sum is considered

B. -1 because the max subarray is the single largest element

C. -10 because sum of all elements is max

D. -4 because last element is max

Solution

1. Step 1: Analyze array with all negative numbers

   All elements are negative, so the max subarray is the one with the least negative value (largest number).

2. Step 2: Identify max element

   The largest element is -1, so max subarray sum is -1 (single element subarray).

3. Final Answer:

   -1 because the max subarray is the single largest element -> Option B

4. Quick Check:

   Max subarray in negatives = max single element [OK]

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

Common Mistakes:

• Assuming sum of all negatives is max
• Considering empty subarray sum as zero incorrectly
• Picking last element without comparison