Find Maximum Subarray Divide and Conquer in DSA C# - Execution Trace

Concept Flow - Find Maximum Subarray Divide and Conquer

Divide array into two halves

↓

Find max subarray in left half

↓

Find max crossing subarray spanning middle

↓

Compare left max, right max, crossing max

↓

Return max of three as result

The array is split into halves recursively. We find max subarrays in left, right, and crossing middle, then pick the largest.

Execution Sample

DSA C#

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

This code finds the maximum sum of a subarray using divide and conquer by splitting, solving halves, and combining.

Execution Table

Step	Operation	Subarray Range	Left Max	Right Max	Cross Max	Max Subarray Sum	Visual State
1	Divide full array	[0..7]	-	-	-	-	[2, -1, 3, 4, -2, 1, -5, 4]
2	Divide left half	[0..3]	-	-	-	-	[2, -1, 3, 4]
3	Divide left-left half	[0..1]	-	-	-	-	[2, -1]
4	Base case left-left-left	[0..0]	2	-	-	2	[2]
5	Base case left-left-right	[1..1]	-1	-	-	-1	[-1]
6	Find cross max [0..1]	[0..1]	2	-1	1	2	[2, -1]
7	Max left-left	[0..1]	2	-1	1	2	[2, -1]
8	Divide left-right half	[2..3]	-	-	-	-	[3, 4]
9	Base case left-right-left	[2..2]	3	-	-	3	[3]
10	Base case left-right-right	[3..3]	4	-	-	4	[4]
11	Find cross max [2..3]	[2..3]	3	4	7	7	[3, 4]
12	Max left-right	[2..3]	3	4	7	7	[3, 4]
13	Find cross max [0..3]	[0..3]	2	7	8	8	[2, -1, 3, 4]
14	Max left half	[0..3]	2	7	8	8	[2, -1, 3, 4]
15	Divide right half	[4..7]	-	-	-	-	[-2, 1, -5, 4]
16	Divide right-left half	[4..5]	-	-	-	-	[-2, 1]
17	Base case right-left-left	[4..4]	-2	-	-	-2	[-2]
18	Base case right-left-right	[5..5]	1	-	-	1	[1]
19	Find cross max [4..5]	[4..5]	-2	1	-1	1	[-2, 1]
20	Max right-left	[4..5]	-2	1	-1	1	[-2, 1]
21	Divide right-right half	[6..7]	-	-	-	-	[-5, 4]
22	Base case right-right-left	[6..6]	-5	-	-	-5	[-5]
23	Base case right-right-right	[7..7]	4	-	-	4	[4]
24	Find cross max [6..7]	[6..7]	-5	4	-1	4	[-5, 4]
25	Max right-right	[6..7]	-5	4	-1	4	[-5, 4]
26	Find cross max [4..7]	[4..7]	1	4	0	4	[-2, 1, -5, 4]
27	Max right half	[4..7]	1	4	0	4	[-2, 1, -5, 4]
28	Find cross max [0..7]	[0..7]	8	4	7	8	[2, -1, 3, 4, -2, 1, -5, 4]
29	Final max subarray sum	[0..7]	8	4	7	8	[2, -1, 3, 4, -2, 1, -5, 4]
30	Exit	-	-	-	-	-	Max subarray sum found: 8

💡 Recursion ends when subarray size is 1; final max sum is 8

Variable Tracker

Variable	Start	After Step 4	After Step 5	After Step 6	After Step 7	After Step 11	After Step 13	After Step 14	After Step 19	After Step 26	After Step 29
low	0	0	0	0	0	0	0	0	4	4	0
high	7	0	1	1	1	3	3	3	5	7	7
mid	3	0	0	0	0	2	1	1	4	5	3
leftMax	-	2	2	2	2	3	8	8	1	1	8
rightMax	-	-1	-1	-1	-1	4	4	4	4	4	4
crossMax	-	-	1	1	1	7	8	8	-1	0	7
maxSubarraySum	-	2	2	2	2	7	8	8	1	4	8

Key Moments - 3 Insights

Why do we need to find the max crossing subarray separately?

Because the maximum subarray might cross the middle point dividing the array. The execution_table rows 6, 11, 13, 26 show how crossing sums are calculated and compared with left and right halves.

What happens when the subarray size is 1?

At this base case (rows 4, 5, 9, 10, 17, 18, 22, 23), the function returns the single element as max sum, stopping further division.

Why do we compare leftMax, rightMax, and crossMax?

Because the maximum subarray can be fully in left half, right half, or crossing the middle. The final max is the largest among these three, as shown in rows 13, 14, 26, 29.

Visual Quiz - 3 Questions

Look at the execution_table at step 13, what is the max subarray sum for the left half [0..3]?

A 8

B 7

C 2

D 4

💡 Hint

Check the 'Max Subarray Sum' column at step 13 in execution_table.

At which step does the recursion reach the base case for the subarray [3..3]?

A Step 23

B Step 5

C Step 10

D Step 18

💡 Hint

Look for the step where low == high == 3 in execution_table.

If the element at index 4 changed from -2 to 5, how would the max subarray sum at step 29 change?

A It would stay 8

B It would increase above 8

C It would decrease below 8

D It would become negative

💡 Hint

Consider how a larger positive number in the middle affects crossing sums in variable_tracker and execution_table.

Concept Snapshot

Divide and conquer splits array into halves.
Find max subarray in left, right, and crossing middle.
Base case: single element subarray.
Return max of leftMax, rightMax, crossMax.
Combines results to find global max subarray sum.

Full Transcript

The divide and conquer method for finding the maximum subarray sum works by splitting the array into two halves recursively. At each step, it finds the maximum subarray sum in the left half, right half, and the subarray crossing the middle. The base case occurs when the subarray has only one element, which is returned as the max sum. The final result is the maximum among these three values. The execution table traces these steps with subarray ranges and sums, showing how the solution builds up. Key moments include understanding why crossing subarrays are checked and how base cases stop recursion. The variable tracker shows how pointers and max sums change at each step. This method efficiently finds the maximum sum subarray by combining smaller solutions.

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