Find Maximum Subarray Divide and Conquer in DSA Python

Mental Model

Split the array into two halves, find the max subarray in the left half, right half, and crossing the middle, then pick the best.

Analogy: Imagine cutting a chocolate bar into two pieces, finding the tastiest part in the left piece, the right piece, and the middle where they meet, then choosing the best bite.

Array: [ -2, 1, -3, 4, -1, 2, 1, -5, 4 ]
Divide: [ -2, 1, -3, 4 ] | [ -1, 2, 1, -5, 4 ]
Find max left, max right, max crossing middle
Choose the biggest sum

Dry Run Walkthrough

Input: array: [-2, 1, -3, 4, -1, 2, 1, -5, 4]

Goal: Find the maximum sum of any continuous subarray using divide and conquer

Step 1: Divide array into left [-2,1,-3,4] and right [-1,2,1,-5,4]

Left: [-2,1,-3,4] | Right: [-1,2,1,-5,4]

Why: We split the problem into smaller parts to solve recursively

Step 2: Find max subarray in left half by dividing again

Left split into [-2,1] and [-3,4]

Why: Divide left half further to find max subarray

Step 3: Find max subarray in [-2,1]: max is 1 (single element)

Max left subarray in [-2,1] is [1] with sum 1

Why: Base case reached with small array

Step 4: Find max subarray in [-3,4]: max is 4 (single element)

Max right subarray in [-3,4] is [4] with sum 4

Why: Base case reached with small array

Step 5: Find max crossing subarray between [-2,1] and [-3,4]

Crossing max subarray is [1,-3,4] with sum 2

Why: Check subarray crossing middle for max sum

Step 6: Choose max of left (1), right (4), crossing (2) -> 4

Max subarray in left half is [4] with sum 4

Why: Pick the best max subarray in left half

Step 7: Find max subarray in right half [-1,2,1,-5,4] by dividing

Right split into [-1,2] and [1,-5,4]

Why: Divide right half further to find max subarray

Step 8: Find max subarray in [-1,2]: max is 2 (single element)

Max left subarray in right half is [2] with sum 2

Why: Base case reached with small array

Step 9: Find max subarray in [1,-5,4]: max is 4 (single element)

Max right subarray in right half is [4] with sum 4

Why: Base case reached with small array

Step 10: Find max crossing subarray between [-1,2] and [1,-5,4]

Crossing max subarray is [2,1] with sum 3

Why: Check subarray crossing middle for max sum

Step 11: Choose max of left (2), right (4), crossing (3) -> 4

Max subarray in right half is [4] with sum 4

Why: Pick the best max subarray in right half

Step 12: Find max crossing subarray crossing whole array middle

Crossing max subarray is [4,-1,2,1] with sum 6

Why: Check subarray crossing the middle of full array

Step 13: Choose max of left half (4), right half (4), crossing (6) -> 6

Max subarray in full array is [4,-1,2,1] with sum 6

Why: Final answer is the best among all three

Result:

4 -> -1 -> 2 -> 1 -> null with sum 6

Annotated Code

DSA Python

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

    def max_subarray_sum(self, arr, left, right):
        if left == right:
            return arr[left], left, right
        mid = (left + right) // 2
        left_sum, left_start, left_end = self.max_subarray_sum(arr, left, mid)
        right_sum, right_start, right_end = self.max_subarray_sum(arr, mid + 1, right)
        cross_sum, cross_start, cross_end = self.max_crossing_sum(arr, left, mid, right)
        if left_sum >= right_sum and left_sum >= cross_sum:
            return left_sum, left_start, left_end
        elif right_sum >= left_sum and right_sum >= cross_sum:
            return right_sum, right_start, right_end
        else:
            return cross_sum, cross_start, cross_end

if __name__ == '__main__':
    arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
    sol = Solution()
    max_sum, start, end = sol.max_subarray_sum(arr, 0, len(arr) - 1)
    print('Max subarray:', ' -> '.join(str(x) for x in arr[start:end+1]) + ' -> null')
    print('Max sum:', max_sum)

for i in range(mid, left - 1, -1):

accumulate sum from middle to left to find max left crossing sum

for j in range(mid + 1, right + 1):

accumulate sum from middle+1 to right to find max right crossing sum

if left == right:

base case: single element subarray

left_sum, left_start, left_end = self.max_subarray_sum(arr, left, mid)

recursively find max subarray in left half

right_sum, right_start, right_end = self.max_subarray_sum(arr, mid + 1, right)

recursively find max subarray in right half

cross_sum, cross_start, cross_end = self.max_crossing_sum(arr, left, mid, right)

find max subarray crossing the middle

if left_sum >= right_sum and left_sum >= cross_sum:

choose the max among left, right, and crossing subarrays

Output

Max subarray: 4 -> -1 -> 2 -> 1 -> null

Max sum: 6

Complexity Analysis

Time: O(n log n) because the array is divided into halves recursively and each merge step takes O(n) to find crossing sums

Space: O(log n) due to recursion stack depth for dividing the array

vs Alternative: Better than naive O(n^2) approach that checks all subarrays; slower than Kadane's O(n) but uses divide and conquer strategy

Edge Cases

empty array

function should not run or handle gracefully; current code assumes non-empty input

DSA Python

if left == right:

array with one element

returns that element as max subarray

DSA Python

if left == right:

all negative numbers

returns the single largest (least negative) element as max subarray

DSA Python

if left == right:

When to Use This Pattern

When asked to find the maximum sum of a continuous subarray and a divide and conquer approach is suggested, use this pattern to split the problem and combine results efficiently.

Common Mistakes

Mistake: Not correctly handling the crossing subarray sums leading to wrong max crossing sum
Fix: Accumulate sums from middle to left and middle+1 to right separately and track max sums carefully

Mistake: Forgetting base case of single element causing infinite recursion
Fix: Add base case check if left == right to return that element

Summary

Finds the maximum sum of any continuous subarray using divide and conquer.

Use when you want a recursive approach splitting the array into halves to find max subarray.

The key insight is to consider max subarrays in left half, right half, and crossing the middle, then pick the best.

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