Find Maximum Subarray Divide and Conquer in DSA Python - Time & Space Complexity

Time Complexity: Find Maximum Subarray Divide and Conquer

O(n log n)

Understanding Time Complexity

We want to understand how the time needed to find the maximum subarray grows as the input size increases.

Specifically, we ask: How does the divide and conquer approach scale with bigger arrays?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

def max_subarray(arr, low, high):
    if low == high:
        return arr[low]
    mid = (low + high) // 2
    left_max = max_subarray(arr, low, mid)
    right_max = max_subarray(arr, mid + 1, high)
    cross_max = max_crossing_subarray(arr, low, mid, high)
    return max(left_max, right_max, cross_max)

This code finds the maximum sum of a contiguous subarray using divide and conquer.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls splitting the array into halves.
• How many times: The array is split into two halves repeatedly until single elements remain, so about log n levels.
• Secondary operation: The crossing subarray calculation loops over elements around the middle once per recursion level.
• How many times: Each level does a linear scan over parts of the array, totaling n operations per level.

How Execution Grows With Input

At each level, the work done is proportional to the size of the current subarray, and the number of levels is about log n.

Input Size (n)	Approx. Operations
10	About 10 * log2(10) ≈ 33
100	About 100 * log2(100) ≈ 664
1000	About 1000 * log2(1000) ≈ 9966

Pattern observation: The operations grow a bit faster than linear but much slower than quadratic, roughly n times log n.

Final Time Complexity

Time Complexity: O(n log n)

This means the time needed grows a little more than directly proportional to the input size, multiplied by the number of times the array is split.

Common Mistake

[X] Wrong: "The divide and conquer method runs in linear time O(n) because it splits the array."

[OK] Correct: Although the array is split, each level still scans parts of the array, so the total work adds up to more than just n operations.

Interview Connect

Understanding this time complexity helps you explain how divide and conquer balances splitting work and combining results efficiently, a key skill in problem solving.

Self-Check

"What if we replaced the crossing subarray calculation with a constant time operation? How would the time complexity change?"

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