Find Maximum Subarray Divide and Conquer in DSA Python - Build from Scratch

Find Maximum Subarray Using Divide and Conquer

📖 Scenario: Imagine you have a list of daily profits and losses from a small shop. You want to find the period where the shop made the most money continuously. This means finding the subarray with the highest sum.

🎯 Goal: Build a program that uses the divide and conquer method to find the maximum sum of a continuous subarray in a list of integers.

📋 What You'll Learn

Create a list called profits with the exact values [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]

Create a helper function called find_max_crossing_subarray that finds the maximum subarray crossing the middle point

Create a recursive function called find_maximum_subarray that uses divide and conquer to find the maximum subarray

Print the maximum subarray sum found by find_maximum_subarray

💡 Why This Matters

🌍 Real World

Finding the maximum subarray is useful in financial analysis to detect the most profitable period in stock prices or sales data.

💼 Career

Understanding divide and conquer algorithms and recursion is important for software engineering roles that involve algorithm design and optimization.

1

Create the profits list

Create a list called profits with these exact values: [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]

DSA Python

# Create the list called profits with the given values
# Your code here

Hint

Use square brackets to create the list and separate numbers with commas.

2

Create the find_max_crossing_subarray function

Create a function called find_max_crossing_subarray that takes arr, low, mid, and high as parameters and returns the maximum sum of a subarray crossing the midpoint.

DSA Python

profits = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]

# Define find_max_crossing_subarray function
# Your code here

Hint

Use two loops: one going left from mid, one going right from mid+1, to find max sums crossing mid.

3

Create the find_maximum_subarray recursive function

Create a recursive function called find_maximum_subarray that takes arr, low, and high as parameters and returns the maximum subarray sum using divide and conquer. Use find_max_crossing_subarray inside it.

DSA Python

profits = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]

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

# Define find_maximum_subarray function
# Your code here

Hint

Use recursion to split the array into halves until one element remains, then combine results using the crossing subarray function.

4

Print the maximum subarray sum

Print the maximum subarray sum by calling find_maximum_subarray with profits, 0, and len(profits) - 1 as arguments.

DSA Python

profits = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]

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

def find_maximum_subarray(arr, low, high):
    if low == high:
        return arr[low]
    else:
        mid = (low + high) // 2
        left_sum = find_maximum_subarray(arr, low, mid)
        right_sum = find_maximum_subarray(arr, mid + 1, high)
        cross_sum = find_max_crossing_subarray(arr, low, mid, high)
        return max(left_sum, right_sum, cross_sum)

# Print the maximum subarray sum
# Your code here

Hint

Call the function with the full range of the list and print the result.

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