Find Maximum Subarray Divide and Conquer in DSA Go - 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 best is chosen.

Execution Sample

DSA Go

func maxSubArray(arr []int, low, high int) int {
  if low == high {
    return arr[low]
  }
  mid := (low + high) / 2
  leftMax := maxSubArray(arr, low, mid)
  rightMax := maxSubArray(arr, mid+1, high)
  crossMax := maxCrossingSubArray(arr, low, mid, high)
  return max(leftMax, rightMax, crossMax)
}

This function finds the maximum subarray sum in arr between low and high using divide and conquer.

Execution Table

Step	Operation	Subarray Range	Max Left	Max Right	Max Crossing	Max Overall	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: maxSubArray([0..0]) = 3	[0..0]	3	-	-	-	[3]
5	Base case: maxSubArray([1..1]) = -2	[1..1]	-	-2	-	-	[-2]
6	Find max crossing subarray [0..1]: maxCrossing = 1	[0..1]	-	-	1	-	[3, -2]
7	Max overall for [0..1] = max(3, -2, 1) = 3	[0..1]	3	-2	1	3	[3, -2]
8	Base case: maxSubArray([2..2]) = 5	[2..2]	5	-	-	-	[5]
9	Find max crossing subarray [0..2]: maxCrossing = 6	[0..2]	3	5	6	-	[3, -2, 5]
10	Max overall for [0..2] = 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: maxSubArray([3..3]) = -1	[3..3]	-1	-	-	-	[-1]
13	Base case: maxSubArray([4..4]) = 6	[4..4]	-	6	-	-	[6]
14	Find max crossing subarray [3..4]: maxCrossing = 5	[3..4]	-	-	5	-	[-1, 6]
15	Max overall for [3..4] = max(-1, 6, 5) = 6	[3..4]	-1	6	5	6	[-1, 6]
16	Find max crossing subarray [0..4]: maxCrossing = 11	[0..4]	6	6	11	-	[3, -2, 5, -1, 6]
17	Max overall for [0..4] = max(6, 6, 11) = 11	[0..4]	6	6	11	11	[3, -2, 5, -1, 6]
18	Return 11 as max subarray sum	[0..4]	6	6	11	11	[3, -2, 5, -1, 6]

💡 All subproblems solved, max subarray sum found as 11

Variable Tracker

Variable	Start	After Step 4	After Step 5	After Step 7	After Step 8	After Step 10	After Step 13	After Step 15	After Step 17	Final
low	0	0	0	0	0	0	3	3	0	0
high	4	0	1	1	2	2	3	4	4	4
mid	-	0	0	0	1	1	3	3	2	2
leftMax	-	3	3	3	3	6	-1	-1	6	6
rightMax	-	-	-2	-2	-	5	6	6	6	6
crossMax	-	-	1	1	-	6	5	5	11	11
maxOverall	-	-	3	3	-	6	6	6	11	11

Key Moments - 3 Insights

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

Because the max 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 maxes.

Why do we return arr[low] when low == high?

This is the base case of recursion where the subarray has one element. The execution_table rows 4, 5, 8, 12, and 13 show these base cases returning single elements.

How do we know when to stop dividing the array?

When the subarray size is 1 (low == high), recursion stops. This is shown in the execution_table base cases where no further division happens.

Visual Quiz - 3 Questions

Look at the execution_table at step 10, what is the max overall subarray sum for range [0..2]?

A 3

B 5

C 6

D 1

💡 Hint

Check the 'Max Overall' column at step 10 in execution_table.

At which step does the max crossing subarray for the entire array [0..4] get calculated?

A Step 14

B Step 16

C Step 9

D Step 7

💡 Hint

Look for the 'Find max crossing subarray [0..4]' operation in execution_table.

If the array was all negative numbers, what would change in the execution_table?

A Base cases would return the least negative number

B Recursion would stop earlier

C Max crossing sums would always be positive

D Max overall would always be zero

💡 Hint

Consider how base cases return single elements as shown in execution_table rows 4,5,8,12,13.

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
Time complexity: O(n log n)

Full Transcript

This visualization shows how the divide and conquer method finds the maximum subarray sum. The array is split into halves until single elements remain. Then, max subarrays are found in left, right, and crossing middle parts. The best among these is chosen at each step. The execution table tracks these steps with subarray ranges and max sums. Variable tracker shows how variables like low, high, mid, and max values change. Key moments clarify why crossing sums are needed and when recursion stops. The quiz tests understanding of these steps. This method efficiently finds the max 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. Split the array into two halves, find max subarray in left, right, and crossing middle, then combine results

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. 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 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 in left, right, crossing middle, combine -> Option A

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
• Confusing divide and conquer with sliding window
• Calculating all subarrays sums directly

2. Which of the following Go function signatures correctly represents the divide and conquer function to find maximum subarray sum in an array arr between indices low and high?

easy

A. func maxSubArray(arr []int, low int high int) int

B. func maxSubArray(arr int[], low int, high int) int

C. func maxSubArray(arr []int, low int, high int) (int, int)

D. func maxSubArray(arr []int, low, high int) int

Solution

1. Step 1: Check Go slice and parameter syntax

   In Go, slices are declared as []int, and multiple parameters of same type can be grouped.

2. Step 2: Identify correct function signature

   func maxSubArray(arr []int, low, high int) int uses correct slice type and groups low, high as int parameters, returning int sum.

3. Final Answer:

   func maxSubArray(arr []int, low, high int) int -> Option D

4. Quick Check:

   Go slice syntax and grouped params = func maxSubArray(arr []int, low, high int) int [OK]

Hint: Use []int for slices and group same-type params [OK]

Common Mistakes:

• Using int[] instead of []int for slices
• Returning multiple values when only sum needed
• Separating same-type parameters unnecessarily

3. What is the output of the following Go code snippet that uses divide and conquer to find maximum subarray sum?

package main
import "fmt"

func maxCrossingSum(arr []int, low, mid, high int) int {
    leftSum := -1 << 31
    sum := 0
    for i := mid; i >= low; i-- {
        sum += arr[i]
        if sum > leftSum {
            leftSum = sum
        }
    }
    rightSum := -1 << 31
    sum = 0
    for j := mid + 1; j <= high; j++ {
        sum += arr[j]
        if sum > rightSum {
            rightSum = sum
        }
    }
    return leftSum + rightSum
}

func maxSubArray(arr []int, low, high int) int {
    if low == high {
        return arr[low]
    }
    mid := (low + high) / 2
    leftMax := maxSubArray(arr, low, mid)
    rightMax := maxSubArray(arr, mid+1, high)
    crossMax := maxCrossingSum(arr, low, mid, high)
    if leftMax >= rightMax && leftMax >= crossMax {
        return leftMax
    } else if rightMax >= leftMax && rightMax >= crossMax {
        return rightMax
    } else {
        return crossMax
    }
}

func main() {
    arr := []int{-2, 1, -3, 4, -1, 2, 1, -5, 4}
    fmt.Println(maxSubArray(arr, 0, len(arr)-1))
}

medium

A. 5

B. 7

C. 6

D. 4

Solution

1. Step 1: Understand the input array and max subarray

   The array is [-2,1,-3,4,-1,2,1,-5,4]. The max subarray is [4,-1,2,1] with sum 6.

2. Step 2: Trace divide and conquer calls

   The function recursively finds max in left, right, and crossing middle, correctly returning 6.

3. Final Answer:

   6 -> Option C

4. Quick Check:

   Max subarray sum = 6 [OK]

Hint: Max subarray for example array is 6 [OK]

Common Mistakes:

• Choosing sum including -5 which lowers total
• Confusing max crossing sum with max overall
• Miscomputing indices for mid and crossing sums

4. Identify the bug in this Go function for finding max crossing sum and select the fix:

func maxCrossingSum(arr []int, low, mid, high int) int {
    leftSum := 0
    sum := 0
    for i := mid; i >= low; i-- {
        sum += arr[i]
        if sum > leftSum {
            leftSum = sum
        }
    }
    rightSum := 0
    sum = 0
    for j := mid + 1; j <= high; j++ {
        sum += arr[j]
        if sum > rightSum {
            rightSum = sum
        }
    }
    return leftSum + rightSum
}

medium

A. Initialize leftSum and rightSum to very small number (e.g. -1<<31) instead of 0

B. Change loops to run from low to mid and mid+1 to high

C. Return max of leftSum and rightSum instead of sum

D. Add 1 to mid when calculating leftSum loop

Solution

1. Step 1: Analyze initialization of leftSum and rightSum

   They start at 0, which fails if all numbers are negative, missing correct max sums.

2. Step 2: Fix initialization to very small number

   Set leftSum and rightSum to -1<<31 (minimum int) to correctly track max sums even if negative.

3. Final Answer:

   Initialize leftSum and rightSum to very small number (e.g. -1<<31) -> Option A

4. Quick Check:

   Proper initialization avoids missing negative max sums [OK]

Hint: Initialize max sums to very small number, not zero [OK]

Common Mistakes:

• Starting max sums at zero causes wrong results with negatives
• Changing loop directions incorrectly
• Returning sum instead of combined max sums

5. Given an array arr of integers, how would you modify the divide and conquer approach to also return the start and end indices of the maximum subarray along with its sum?

hard

A. Store indices globally and update them only when crossing sum is calculated

B. Change functions to return a struct with sum, start, and end; update recursive calls to track indices

C. Return only sum and find indices by scanning array after result

D. Use a separate loop after divide and conquer to find indices of max sum

Solution

1. Step 1: Modify function return types

   Change functions to return a struct containing sum, start index, and end index to track subarray boundaries.

2. Step 2: Update recursive calls and combine logic

   When combining left, right, and crossing results, also combine their indices accordingly to keep track of max subarray range.

3. Final Answer:

   Return struct with sum, start, end; update recursive calls to track indices -> Option B

4. Quick Check:

   Return sum and indices together for full max subarray info [OK]

Hint: Return sum plus indices in struct, update recursively [OK]

Common Mistakes:

• Using global variables causing bugs in recursion
• Finding indices after sum calculation separately
• Ignoring indices in crossing sum calculation