Find Maximum Subarray Divide and Conquer in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to find the midpoint of the array segment.

DSA Python

def find_max_subarray(arr, low, high):
    if low == high:
        return arr[low]
    mid = (low + high) [1] 2
    # further code omitted

Drag options to blanks, or click blank then click option'

A+

B-

C//

D*

Attempts:

3 left

💡 Hint

Common Mistakes

Using '+' instead of division causes wrong midpoint.

Using '*' or '-' does not find midpoint.

We use integer division '//' to get the midpoint index between low and high.

2fill in blank

medium

Complete the code to find the maximum crossing subarray sum.

DSA Python

def max_crossing_sum(arr, low, mid, high):
    left_sum = float('-inf')
    sum = 0
    for i in range(mid, low - 1, -1):
        sum += arr[i]
        if sum [1] left_sum:
            left_sum = sum
    # further code omitted

Drag options to blanks, or click blank then click option'

A<

B<=

C==

D>

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' instead of '>' causes no update to left_sum.

Using '==' misses larger sums.

We update left_sum when current sum is greater than left_sum.

3fill in blank

hard

Fix the error in the recursive call to find maximum subarray sum.

DSA Python

def find_max_subarray(arr, low, high):
    if low == high:
        return arr[low]
    mid = (low + high) // 2
    left_sum = find_max_subarray(arr, low, [1])
    right_sum = find_max_subarray(arr, mid + 1, high)
    # further code omitted

Drag options to blanks, or click blank then click option'

Amid

Bhigh

Clow

Dmid + 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'high' causes overlap with right half.

Using 'mid + 1' in left call causes empty segment.

The left recursive call should cover from low to mid.

4fill in blank

hard

Fill both blanks to return the maximum of three sums.

DSA Python

def find_max_subarray(arr, low, high):
    # code omitted
    return max([1], [2], max_crossing_sum(arr, low, mid, high))

Drag options to blanks, or click blank then click option'

Aleft_sum

Bright_sum

Cmid

Dcross_sum

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'mid' or 'cross_sum' instead of left_sum or right_sum.

Not including all three sums in max function.

We compare left_sum, right_sum, and crossing sum to find the max.

5fill in blank

hard

Fill all three blanks to complete the max_crossing_sum function.

DSA Python

def max_crossing_sum(arr, low, mid, high):
    left_sum = float('-inf')
    sum = 0
    for i in range(mid, [1], -1):
        sum += arr[i]
        if sum > left_sum:
            left_sum = sum
    right_sum = float('-inf')
    sum = 0
    for j in range(mid + 1, [2]):
        sum += arr[j]
        if sum > right_sum:
            right_sum = sum
    return left_sum + right_sum

# Call example: max_crossing_sum(arr, 0, 3, [3])

Drag options to blanks, or click blank then click option'

Alow - 1

Bhigh + 1

Chigh

Dlow

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'low' instead of 'low - 1' causes missing first element.

Using 'high' instead of 'high + 1' causes missing last element.

Passing wrong high index in call.

The left loop goes down to low - 1 (exclusive), right loop goes up to high + 1 (exclusive), and high is the last index.

Practice

1. What is the main idea behind the Divide and Conquer approach to find the maximum subarray sum?

easy

A. Sort the array and pick the largest element

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

C. Use a sliding window to find the maximum sum

D. Calculate sum of all subarrays and pick the maximum

Solution

1. Step 1: Understand the divide step

   The array is split into two halves to simplify the problem into smaller parts.

2. Step 2: Combine results from subproblems

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

3. Final Answer:

   Divide the array into two halves, find max subarray in left, right, and crossing middle, then combine results -> Option B

4. Quick Check:

   Divide and conquer = split, solve, combine [OK]

Hint: Split array, solve halves, check crossing sum [OK]

Common Mistakes:

• Thinking sorting helps find max subarray
• Ignoring the crossing middle subarray
• Trying to sum all subarrays directly

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

easy

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

B. If the array length is 1, return 0

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

D. If the array length is 0, return 0

Solution

1. Step 1: Identify the smallest problem size

   The smallest subarray is a single element, so when length is 1, we return that element.

2. Step 2: Understand base case return value

   Return the single element because it is the maximum subarray sum for that subarray.

3. Final Answer:

   If the array length is 1, return the single element -> Option A

4. Quick Check:

   Base case = single element value [OK]

Hint: Base case returns single element value [OK]

Common Mistakes:

• Returning 0 instead of element for length 1
• Returning sum of two elements as base case
• Ignoring base case and causing infinite recursion

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

def max_crossing_sum(arr, left, mid, right):
    left_sum = float('-inf')
    total = 0
    for i in range(mid, left-1, -1):
        total += arr[i]
        if total > left_sum:
            left_sum = total
    right_sum = float('-inf')
    total = 0
    for j in range(mid+1, right+1):
        total += arr[j]
        if total > right_sum:
            right_sum = total
    return left_sum + right_sum

def max_subarray(arr, left, right):
    if left == right:
        return arr[left]
    mid = (left + right) // 2
    left_max = max_subarray(arr, left, mid)
    right_max = max_subarray(arr, mid+1, right)
    cross_max = max_crossing_sum(arr, left, mid, right)
    return max(left_max, right_max, cross_max)

arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray(arr, 0, len(arr)-1))

medium

A. 6

B. 7

C. 5

D. 4

Solution

1. Step 1: Understand the input array and function

   The array is [-2, 1, -3, 4, -1, 2, 1, -5, 4]. The function finds max subarray sum using divide and conquer.

2. Step 2: Calculate maximum subarray sum manually

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

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Max subarray sum = 6 [OK]

Hint: Look for max sum in continuous subarray [OK]

Common Mistakes:

• Choosing sum including -5 which lowers total
• Confusing max crossing sum with max overall
• Miscomputing indices in loops

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

def max_crossing_sum(arr, left, mid, right):
    left_sum = 0
    total = 0
    for i in range(mid, left-1, -1):
        total += arr[i]
        if total > left_sum:
            left_sum = total
    right_sum = 0
    total = 0
    for j in range(mid+1, right+1):
        total += arr[j]
        if total > right_sum:
            right_sum = total
    return left_sum + right_sum

medium

A. The total variable should not be reset inside the loops

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

C. The function should return max(left_sum, right_sum), not their sum

D. left_sum and right_sum should start at negative infinity, not 0

Solution

1. Step 1: Analyze initial values of left_sum and right_sum

   They start at 0, which fails if all numbers are negative because max sum could be negative.

2. Step 2: Correct initialization

   Initialize left_sum and right_sum to negative infinity to correctly track max sums even if negative.

3. Final Answer:

   left_sum and right_sum should start at negative infinity, not 0 -> Option D

4. Quick Check:

   Init max sums to -inf to handle negatives [OK]

Hint: Use -inf for max sums to handle negative values [OK]

Common Mistakes:

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

5. Given an array arr = [3, -2, 5, -1, 6, -3, 2, 7, -5, 2], what is the maximum subarray sum found using divide and conquer? Also, which subarray produces this sum?

hard

A. Sum = 16, Subarray = [5, -1, 6, -3, 2, 7, -5, 2]

B. Sum = 14, Subarray = [5, -1, 6, -3, 2, 7]

C. Sum = 17, Subarray = [3, -2, 5, -1, 6, -3, 2, 7]

D. Sum = 18, Subarray = [3, -2, 5, -1, 6, -3, 2, 7, -5, 2]

Solution

1. Step 1: Calculate sums of candidate subarrays

   Check sums of given subarrays: - Sum = 14, Subarray = [5, -1, 6, -3, 2, 7]: 5 + (-1) + 6 + (-3) + 2 + 7 = 16 (not 14) - Sum = 17, Subarray = [3, -2, 5, -1, 6, -3, 2, 7]: 3 + (-2) + 5 + (-1) + 6 + (-3) + 2 + 7 = 17 - Sum = 16, Subarray = [5, -1, 6, -3, 2, 7, -5, 2]: 5 + (-1) + 6 + (-3) + 2 + 7 + (-5) + 2 = 13 (not 16) - Sum = 18, Subarray = [3, -2, 5, -1, 6, -3, 2, 7, -5, 2]: sum of entire array = 3 -2 +5 -1 +6 -3 +2 +7 -5 +2 = 14 (not 18)

2. Step 2: Identify maximum sum and subarray

   The maximum sum is 17 from subarray [3, -2, 5, -1, 6, -3, 2, 7].

3. Final Answer:

   Sum = 17, Subarray = [3, -2, 5, -1, 6, -3, 2, 7] -> Option C

4. Quick Check:

   Max sum = 17 from longest subarray [OK]

Hint: Sum subarrays carefully, check all candidates [OK]

Common Mistakes:

• Miscomputing sums with negative numbers
• Assuming max sum is entire array sum
• Ignoring subarray boundaries