Find Maximum Subarray Divide and Conquer in DSA Java - 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, max subarrays are found in left, right, and crossing middle, then the maximum of these is returned.

Execution Sample

DSA Java

public class MaxSubarray {
  public static int maxSubArray(int[] arr, int low, int high) {
    if (low == high) return arr[low];
    int mid = (low + high) / 2;
    int leftMax = maxSubArray(arr, low, mid);
    int rightMax = maxSubArray(arr, mid + 1, high);
    int crossMax = maxCrossingSubarray(arr, low, mid, high);
    return Math.max(Math.max(leftMax, rightMax), crossMax);
  }

  private static int maxCrossingSubarray(int[] arr, int low, int mid, int high) {
    int leftSum = 0;
    int maxLeft = Integer.MIN_VALUE;
    for (int i = mid; i >= low; i--) {
      leftSum += arr[i];
      if (leftSum > maxLeft) maxLeft = leftSum;
    }
    int rightSum = 0;
    int maxRight = Integer.MIN_VALUE;
    for (int i = mid + 1; i <= high; i++) {
      rightSum += arr[i];
      if (rightSum > maxRight) maxRight = rightSum;
    }
    return maxLeft + maxRight;
  }
}

This code finds the maximum sum subarray in arr between low and high using divide and conquer, with a helper method for max crossing subarray.

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]	[0..4]	-	-	-	-	[7, -2, 3, -1, 2]
2	Divide left half [0..2]	[0..2]	-	-	-	-	[7, -2, 3]
3	Divide left half of left [0..1]	[0..1]	-	-	-	-	[7, -2]
4	Base case single element [0..0]	[0..0]	7	-	-	7	[7]
5	Base case single element [1..1]	[1..1]	-2	-	-	-2	[-2]
6	Find crossing max [0..1]	[0..1]	7	-2	5	7	[7, -2]
7	Max subarray [0..1]	[0..1]	7	-2	5	7	[7, -2]
8	Base case single element [2..2]	[2..2]	3	-	-	3	[3]
9	Find crossing max [0..2]	[0..2]	7	3	8	8	[7, -2, 3]
10	Max subarray [0..2]	[0..2]	7	3	8	8	[7, -2, 3]
11	Divide right half [3..4]	[3..4]	-	-	-	-	[-1, 2]
12	Base case single element [3..3]	[3..3]	-1	-	-	-1	[-1]
13	Base case single element [4..4]	[4..4]	2	-	-	2	[2]
14	Find crossing max [3..4]	[3..4]	-1	2	1	2	[-1, 2]
15	Max subarray [3..4]	[3..4]	-1	2	1	2	[-1, 2]
16	Find crossing max [0..4]	[0..4]	8	2	9	9	[7, -2, 3, -1, 2]
17	Max subarray [0..4]	[0..4]	8	2	9	9	[7, -2, 3, -1, 2]
18	Return final max subarray sum	[0..4]	8	2	9	9	[7, -2, 3, -1, 2]

💡 All subproblems solved, final max subarray sum is 9

Variable Tracker

Variable	Start	After Step 4	After Step 5	After Step 6	After Step 8	After Step 9	After Step 12	After Step 13	After Step 14	After Step 16	Final
low	0	0	1	0	2	0	3	4	3	0	0
high	4	0	1	1	2	2	3	4	4	4	4
mid	-	0	0	0	1	1	3	3	3	2	2
leftMax	-	7	7	7	8	8	-1	-1	-1	8	8
rightMax	-	-	-2	-2	3	3	-	2	2	2	2
crossMax	-	-	5	5	-	8	-	-	1	9	9
maxSubarraySum	-	7	7	7	8	8	2	2	2	9	9

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, 9, 14, and 16 show how crossing sums are calculated and compared with left and right max sums.

Why does the base case return the single element value?

When low equals high, the subarray has one element, so the max sum is that element itself. See execution_table rows 4, 5, 8, 12, and 13 where base cases return single elements.

How do we know which max sum to return at each step?

We compare leftMax, rightMax, and crossMax and return the largest. This is shown in execution_table rows 7, 10, 15, and 17 where the maxSubarraySum is chosen.

Visual Quiz - 3 Questions

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

A 8

B 7

C 5

D 3

💡 Hint

Check the 'Max Crossing Sum' column in row 9 of execution_table.

At which step does the condition low == high first occur?

A Step 6

B Step 9

C Step 4

D Step 12

💡 Hint

Look for base case rows where subarray range is a single element.

If the array was all negative numbers, how would the maxSubarraySum change in the variable_tracker?

A It would always be zero

B It would be the least negative single element

C It would be the sum of all elements

D It would be the max crossing sum

💡 Hint

Recall base case returns single element; max sum in negatives is the largest single element.

Concept Snapshot

Divide array into halves recursively
Find max subarray in left half, right half, and crossing middle
Return max of these three
Base case: single element subarray
Crossing max 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 until single elements remain. For each subarray, it finds the maximum subarray sum in the left half, right half, and the subarray crossing the middle. The maximum of these three sums is returned. The base case is when the subarray has one element, returning that element's value. The crossing subarray sum is found by expanding from the middle to left and right, summing elements to find the max crossing sum. This process continues up the recursion tree until the entire array's maximum subarray sum is found. The execution table shows each step's subarray range, sums, and decisions. The variable tracker follows key variables like low, high, mid, and max sums. Key moments clarify why crossing sums are needed, base case logic, and how max sums are chosen. The quiz tests understanding of crossing sums, base cases, and behavior with negative numbers.

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

C. Split 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 the maximum sum

Solution

1. Step 1: Understand divide and conquer strategy

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

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

4. Quick Check:

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

Hint: Divide array, solve halves, combine crossing max [OK]

Common Mistakes:

• Thinking sorting helps find max subarray sum
• Confusing divide and conquer with sliding window
• Ignoring subarrays crossing the middle

2. Which of the following is the correct base case for the recursive function in the divide and conquer approach to find the maximum subarray?

easy

A. When the array is empty, return 0

B. When the array has only one element, return that element

C. When the array has two elements, return their sum

D. When the array has more than one element, return the max of left and right

Solution

1. Step 1: Identify base case for recursion

   The recursion stops when the subarray has only one element.

2. Step 2: Return the single element as max subarray sum

   Since one element is the smallest subarray, return it directly.

3. Final Answer:

   Return single element when array size is one -> Option B

4. Quick Check:

   Base case = single element return [OK]

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

Common Mistakes:

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

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

int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
System.out.println(maxSubArray(arr, 0, arr.length - 1));

// Assume maxSubArray is correctly implemented divide and conquer method

medium

A. 4

B. 7

C. 5

D. 6

Solution

1. Step 1: Identify max subarray in given array

   The max subarray is [4, -1, 2, 1] with sum 4 + (-1) + 2 + 1 = 6.

2. Step 2: Check if any larger sum exists

   Adding the next element -5 or 4 does not increase sum beyond 6, but including the last 4 gives total 5 for subarray [4, -1, 2, 1, -5, 4]?

3. Step 3: Correct max subarray is [4, -1, 2, 1] with sum 6

   Actually, the max sum is 6, not 5.

4. Final Answer:

   6 -> Option D

5. Quick Check:

   Max subarray sum = 6 [OK]

Hint: Find max sum subarray by checking sums around middle [OK]

Common Mistakes:

• Choosing sum including negative elements that reduce total
• Miscounting elements in max subarray
• Confusing max sum with max element

4. Identify the error in this divide and conquer code snippet for max subarray sum:

int maxCrossingSum(int[] arr, int left, int mid, int right) {
    int sum = 0, left_sum = Integer.MIN_VALUE;
    for (int i = mid; i >= left; i--) {
        sum += arr[i];
        if (sum > left_sum) left_sum = sum;
    }
    sum = 0;
    int right_sum = Integer.MIN_VALUE;
    for (int i = mid + 1; i <= right; i++) {
        sum += arr[i];
        if (sum > right_sum) right_sum = sum;
    }
    return left_sum + right_sum;
}

medium

A. No error, code correctly finds max crossing sum

B. Should initialize sum to Integer.MIN_VALUE instead of 0

C. Return statement should be max of left_sum and right_sum, not sum

D. Loop ranges are incorrect; should start from left+1 and mid-1

Solution

1. Step 1: Analyze loops for left and right sums

   Loops correctly accumulate sums from mid to left and mid+1 to right.

2. Step 2: Check return statement

   Returns sum of max left and right sums crossing mid, which is correct for crossing subarray.

3. Final Answer:

   No error, code correctly finds max crossing sum -> Option A

4. Quick Check:

   Crossing sum = left max + right max [OK]

Hint: Crossing sum = max left + max right sums around mid [OK]

Common Mistakes:

• Initializing sum to wrong value causing incorrect sums
• Returning max instead of sum of left and right max
• Incorrect loop boundaries skipping elements

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

hard

A. -1

B. -10

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

2. Step 2: Identify largest element in array

   Largest element is -1, so max subarray sum is -1.

3. Final Answer:

   -1 -> Option A

4. Quick Check:

   Max subarray sum with negatives = max element [OK]

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

Common Mistakes:

• Summing all negatives instead of picking max element
• Returning zero incorrectly assuming empty subarray
• Confusing max subarray sum with min element