Find Maximum Subarray Divide and Conquer in DSA C#

Mental Model

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

Analogy: Imagine you have a long road with some good and bad spots. You want to find the best continuous stretch. You check the left side, the right side, and the middle crossing point, then choose the best stretch overall.

Array: [ -2, 1, -3, 4, -1, 2, 1, -5, 4 ]
Divide: [ -2, 1, -3, 4 ] | [ -1, 2, 1, -5, 4 ]
Middle:          ↑
Max subarray could be in left, right, or crossing middle.

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: Divide 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: 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 subarray in left half

Step 3: Find max subarray in right half recursively

Right max subarray: [4] with sum 4

Why: Find max subarray 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 (4), crossing max (6) and pick max

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

Why: Choose the best among three

Result:

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

Annotated Code

DSA C#

using System;

class MaxSubarrayDivideConquer
{
    public static int FindMaxCrossingSubarray(int[] arr, int low, int mid, int high)
    {
        int leftSum = int.MinValue;
        int sum = 0;
        for (int i = mid; i >= low; i--)
        {
            sum += arr[i];
            if (sum > leftSum)
                leftSum = sum; // max sum on left side
        }

        int rightSum = int.MinValue;
        sum = 0;
        for (int j = mid + 1; j <= high; j++)
        {
            sum += arr[j];
            if (sum > rightSum)
                rightSum = sum; // max sum on right side
        }

        return leftSum + rightSum; // max crossing sum
    }

    public static int FindMaxSubarray(int[] arr, int low, int high)
    {
        if (low == high)
            return arr[low]; // base case single element

        int mid = (low + high) / 2;

        int leftMax = FindMaxSubarray(arr, low, mid); // max in left half
        int rightMax = FindMaxSubarray(arr, mid + 1, high); // max in right half
        int crossMax = FindMaxCrossingSubarray(arr, low, mid, high); // max crossing mid

        return Math.Max(Math.Max(leftMax, rightMax), crossMax); // best of three
    }

    static void Main()
    {
        int[] arr = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
        int maxSum = FindMaxSubarray(arr, 0, arr.Length - 1);
        Console.WriteLine(maxSum);
    }
}

for (int i = mid; i >= low; i--) { sum += arr[i]; if (sum > leftSum) leftSum = sum; // max sum on left side }

Find max sum subarray ending at mid going left

for (int j = mid + 1; j <= high; j++) { sum += arr[j]; if (sum > rightSum) rightSum = sum; // max sum on right side }

Find max sum subarray starting at mid+1 going right

if (low == high) return arr[low]; // base case single element

Stop recursion when one element left

int leftMax = FindMaxSubarray(arr, low, mid); // max in left half

Recursively find max subarray in left half

int rightMax = FindMaxSubarray(arr, mid + 1, high); // max in right half

Recursively find max subarray in right half

int crossMax = FindMaxCrossingSubarray(arr, low, mid, high); // max crossing mid

Find max subarray crossing middle

return Math.Max(Math.Max(leftMax, rightMax), crossMax); // best of three

Return the maximum of left, right, and crossing sums

Output

6

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 proportional to log n

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

Edge Cases

Array with single element

Returns that element as max subarray sum

DSA C#

if (low == high)
    return arr[low]; // base case single element

Array with all negative numbers

Returns the largest (least negative) single element

DSA C#

if (low == high)
    return arr[low]; // base case single element

Empty array

Not handled explicitly; would cause error due to invalid indices

DSA C#

No explicit guard; input array must be non-empty

When to Use This Pattern

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

Common Mistakes

Mistake: Not including the crossing subarray in the comparison, missing max subarrays that cross the middle
Fix: Always compute and compare the max crossing subarray sum along with left and right halves

Mistake: Incorrectly calculating the mid index causing infinite recursion or wrong splits
Fix: Calculate mid as (low + high) / 2 and ensure base case stops recursion

Summary

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

Use when you want a recursive approach splitting the array into halves to find max subarray.

The key insight is to consider max subarrays 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. Calculate sum of all subarrays and pick the maximum

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

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

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

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 subproblems

   Find max subarray in left half, right half, and crossing the middle, then take the maximum of these three.

3. Final Answer:

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

4. Quick Check:

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

Hint: Divide array, conquer halves, combine max sums [OK]

Common Mistakes:

• Thinking sorting helps find max subarray sum
• Using brute force sum of all subarrays
• Confusing divide and conquer with sliding window

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

easy

A. If the array length is 0, return 0

B. If the array length is 1, return the single element

C. If the array length is 2, return the sum of both elements

D. If the array length is 1, return 0

Solution

1. Step 1: Identify base case for recursion

   When the array has only one element, that element itself is the max subarray sum.

2. Step 2: Return the single element value

   Return the value of that single element as the maximum sum.

3. Final Answer:

   Return single element when array length is 1 -> Option B

4. Quick Check:

   Base case = single element value [OK]

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

Common Mistakes:

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

3. What will be 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 maxSum = FindMaxSubarray(arr, 0, arr.Length - 1);
Console.WriteLine(maxSum);

int FindMaxSubarray(int[] a, int left, int right) {
    if (left == right) return a[left];
    int mid = (left + right) / 2;
    int leftMax = FindMaxSubarray(a, left, mid);
    int rightMax = FindMaxSubarray(a, mid + 1, right);
    int crossMax = FindMaxCrossingSubarray(a, left, mid, right);
    return Math.Max(Math.Max(leftMax, rightMax), crossMax);
}

int FindMaxCrossingSubarray(int[] a, int left, int mid, int right) {
    int leftSum = int.MinValue, sum = 0;
    for (int i = mid; i >= left; i--) {
        sum += a[i];
        if (sum > leftSum) leftSum = sum;
    }
    int rightSum = int.MinValue;
    sum = 0;
    for (int j = mid + 1; j <= right; j++) {
        sum += a[j];
        if (sum > rightSum) rightSum = sum;
    }
    return leftSum + rightSum;
}

medium

A. 6

B. 7

C. 5

D. 4

Solution

1. Step 1: Identify the maximum subarray sum

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

2. Step 2: Trace the code execution

   Split at mid=4: leftMax (0-4) = 4, rightMax (5-8) = 4, crossMax = 6 ([3-6]). Returns Math.Max(4, 4, 6) = 6.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   max(leftMax=4, rightMax=4, crossMax=6) = 6 [OK]

Hint: Trace subarray sums carefully to find max [OK]

Common Mistakes:

• Miscomputing crossing sum
• Confusing max subarray with max element
• Ignoring negative numbers impact

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

int FindMaxCrossingSubarray(int[] a, int left, int mid, int right) {
    int leftSum = 0, sum = 0;
    for (int i = mid; i >= left; i--) {
        sum += a[i];
        if (sum > leftSum) leftSum = sum;
    }
    int rightSum = 0;
    sum = 0;
    for (int j = mid + 1; j <= right; j++) {
        sum += a[j];
        if (sum > rightSum) rightSum = sum;
    }
    return leftSum + rightSum;
}

medium

A. leftSum and rightSum should be initialized to int.MinValue, not 0

B. The loops should run from left to mid and mid+1 to right respectively

C. sum variable should not be reset between loops

D. The function should return max of leftSum and rightSum, not their sum

Solution

1. Step 1: Check initialization of leftSum and rightSum

   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.MinValue

   Initialize leftSum and rightSum to int.MinValue to correctly track max sums even if negative.

3. Final Answer:

   Initialize leftSum and rightSum to int.MinValue -> Option A

4. Quick Check:

   Init max sums to int.MinValue to handle negatives [OK]

Hint: Init max sums to int.MinValue to handle negatives [OK]

Common Mistakes:

• Initializing max sums to 0 causing wrong results
• Resetting sum incorrectly between loops
• Returning sum instead of max in crossing function

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

hard

A. -4

B. 0

C. -1

D. -10

Solution

1. Step 1: Analyze array with all negative numbers

   All elements are negative, so max subarray is the single largest element.

2. Step 2: Identify largest element

   The largest element is -1, which is the max subarray sum.

3. Final Answer:

   -1 -> Option C

4. Quick Check:

   Max subarray in negatives = max element [OK]

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

Common Mistakes:

• Returning 0 instead of max negative element
• Summing all negatives incorrectly
• Assuming empty subarray sum is allowed