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

↓

If array size is 1, return that element

The array is split into halves recursively. For each part, find max subarray in left, right, and crossing middle. Return the largest.

Execution Sample

DSA C++

int maxCrossingSum(int arr[], int left, int mid, int right) {
  int sum = 0, left_sum = INT_MIN;
  for (int i = mid; i >= left; i--) {
    sum += arr[i];
    if (sum > left_sum) left_sum = sum;
  }
  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;
  }
  return left_sum + right_sum;
}

This function finds max subarray sum crossing the middle index.

Execution Table

Step	Operation	Subarray Range	Max Left Sum	Max Right Sum	Max Crossing Sum	Max Subarray Sum	Visual State
1	Divide array [0..4] into [0..2] and [3..4]	[0..4]	-	-	-	-	[3, -2, 5, -1, 6]
2	Divide left half [0..2] into [0..1] and [2..2]	[0..2]	-	-	-	-	[3, -2, 5]
3	Divide [0..1] into [0..0] and [1..1]	[0..1]	-	-	-	-	[3, -2]
4	Base case: single element at [0..0]	[0..0]	3	-	-	3	[3]
5	Base case: single element at [1..1]	[1..1]	-2	-	-	-2	[-2]
6	Find max crossing sum at mid=0 for [0..1]	[0..1]	3	-2	1	-	[3, -2]
7	Max subarray in [0..1] is max(3, -2, 1) = 3	[0..1]	3	-2	1	3	[3, -2]
8	Base case: single element at [2..2]	[2..2]	5	-	-	5	[5]
9	Find max crossing sum at mid=1 for [0..2]	[0..2]	3	5	6	-	[3, -2, 5]
10	Max subarray in [0..2] is max(3, 5, 6) = 6	[0..2]	3	5	6	6	[3, -2, 5]
11	Divide right half [3..4] into [3..3] and [4..4]	[3..4]	-	-	-	-	[-1, 6]
12	Base case: single element at [3..3]	[3..3]	-1	-	-	-1	[-1]
13	Base case: single element at [4..4]	[4..4]	6	-	-	6	[6]
14	Find max crossing sum at mid=3 for [3..4]	[3..4]	-1	6	5	-	[-1, 6]
15	Max subarray in [3..4] is max(-1, 6, 5) = 6	[3..4]	-1	6	5	6	[-1, 6]
16	Find max crossing sum at mid=2 for [0..4]	[0..4]	6	6	11	-	[3, -2, 5, -1, 6]
17	Max subarray in [0..4] is max(6, 6, 11) = 11	[0..4]	6	6	11	11	[3, -2, 5, -1, 6]
18	Return final max subarray sum 11	[0..4]	6	6	11	11	[3, -2, 5, -1, 6]

💡 All subproblems solved, final max subarray sum found.

Variable Tracker

Variable	Start	After Step 4	After Step 5	After Step 7	After Step 8	After Step 10	After Step 12	After Step 15	After Step 17	Final
left	0	0	0	0	0	0	3	3	0	0
mid	-	0	0	0	2	2	3	3	2	2
right	4	1	1	1	2	2	4	4	4	4
maxLeftSum	-	3	3	3	5	6	-1	-1	6	6
maxRightSum	-	-2	-2	-2	-	5	-	6	6	6
maxCrossingSum	-	-	1	1	-	6	-	5	11	11
maxSubarraySum	-	-	3	3	5	6	-1	6	11	11

Key Moments - 3 Insights

Why do we calculate max crossing sum separately?

Because the max subarray might cross the middle point, so we must check sums that span both halves (see steps 6, 9, 14, 16 in execution_table).

Why do we return the max of left, right, and crossing sums?

Because the maximum subarray can be fully in left half, right half, or crossing the middle. We compare all three to find the true max (see steps 7, 10, 15, 17).

What happens at the base case when array size is 1?

We return the single element as max subarray sum directly (see steps 4, 5, 8, 12, 13). This stops recursion.

Visual Quiz - 3 Questions

Look at the execution_table at step 16, what is the max crossing sum for subarray [0..4]?

A 5

B 6

C 11

D 3

💡 Hint

Check the 'Max Crossing Sum' column at step 16 in execution_table.

At which step does the recursion reach the base case for element at index 2?

A Step 12

B Step 8

C Step 4

D Step 16

💡 Hint

Look for base case steps with single element subarrays in execution_table.

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

A It would increase

B It would decrease

C It would stay 10

D It would become negative

💡 Hint

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

Concept Snapshot

Divide array into halves recursively
Find max subarray in left, right, and crossing middle
Return max of these three
Base case: single element returns itself
Crossing sum found by expanding from middle outwards
Time complexity: O(n log n)

Full Transcript

The divide and conquer method splits the array into two halves repeatedly. For each half, it finds the maximum subarray sum recursively. It also finds the maximum subarray sum that crosses the middle point by expanding sums from the middle to left and right. The final maximum subarray sum is the largest among left half, right half, and crossing sums. The base case occurs when the subarray has one element, which is returned as the max sum. This approach efficiently finds the maximum subarray sum in O(n log n) time.

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