Find Maximum Subarray Divide and Conquer in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind the Divide and Conquer approach for finding the maximum subarray?

Split the array into two halves, find the maximum subarray in the left half, the right half, and the maximum subarray crossing the middle, then return the maximum of these three.

intermediate

In the Divide and Conquer method, how do we find the maximum subarray crossing the middle point?

Find the maximum sum subarray ending at the middle from the left side and the maximum sum subarray starting at the middle+1 from the right side, then add these two sums.

intermediate

What is the time complexity of the Divide and Conquer algorithm for maximum subarray?

O(n log n), because the array is divided into halves recursively and the crossing subarray is found in linear time at each level.

beginner

Why is the maximum subarray problem a good example to teach Divide and Conquer?

Because it clearly shows how a problem can be split into smaller parts, solved independently, and combined to get the final answer.

beginner

What are the three cases considered in the Divide and Conquer maximum subarray algorithm?

1) Maximum subarray lies entirely in the left half, 2) Maximum subarray lies entirely in the right half, 3) Maximum subarray crosses the middle point.

What does the Divide and Conquer algorithm do first when finding the maximum subarray?

A Splits the array into two halves

B Finds the maximum element

C Sorts the array

D Calculates the sum of all elements

The algorithm starts by splitting the array into two halves to apply divide and conquer.

How is the maximum crossing subarray found?

A By checking all subarrays crossing the middle in O(n^2)

B By using dynamic programming

C By sorting the array

D By finding max sum on left side ending at middle and max sum on right side starting at middle+1

The crossing subarray is found by combining max sums from left and right sides around the middle.

What is the time complexity of the Divide and Conquer maximum subarray algorithm?

A O(n log n)

B O(n^2)

C O(n)

D O(log n)

The algorithm divides the problem recursively and does linear work at each level, resulting in O(n log n).

Which of these is NOT a case considered in the Divide and Conquer maximum subarray algorithm?

A Maximum subarray in right half

B Maximum subarray with all negative numbers

C Maximum subarray crossing the middle

D Maximum subarray in left half

The algorithm considers left, right, and crossing subarrays, not specifically all negative numbers.

Why is the maximum subarray problem suitable for Divide and Conquer?

A Because it requires dynamic programming

B Because it can be solved by sorting

C Because it can be split into smaller subproblems and combined

D Because it needs hashing

Divide and Conquer works well because the problem can be split and combined easily.

Explain the steps of the Divide and Conquer algorithm to find the maximum subarray.

Think about how the problem is divided and how results are combined.

Describe how to find the maximum subarray that crosses the middle point in the Divide and Conquer approach.

Focus on sums around the middle index.

Practice

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

easy

A. Use a sliding window to find the maximum sum subarray in one pass

B. Sort the array and pick the largest element as max subarray sum

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

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 left, right, and crossing subarrays

   We find max subarray sums in left half, right half, and subarrays crossing the middle, then take the maximum of these.

3. Final Answer:

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

4. Quick Check:

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

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

Common Mistakes:

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

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

easy

A. if (low == high) return 0;

B. if (low > high) return 0;

C. if (low < high) return arr[low] + arr[high];

D. if (low == high) return arr[low];

Solution

1. Step 1: Identify base case meaning

   When the subarray has only one element (low equals high), the max subarray sum is that element itself.

2. Step 2: Match base case condition

   The condition if (low == high) return arr[low]; correctly returns the single element's value.

3. Final Answer:

   if (low == high) return arr[low]; -> Option D

4. Quick Check:

   Single element subarray returns element value [OK]

Hint: Base case: one element means return that element [OK]

Common Mistakes:

• Returning 0 when low == high
• Using incorrect comparison operators
• Returning sum of two elements instead of one

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

int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
int result = maxSubArray(arr, 0, 8);
printf("%d", result);

Assume maxSubArray is correctly implemented divide and conquer function.

medium

A. 6

B. 7

C. 5

D. 4

Solution

1. Step 1: Identify max subarray in given array

   The maximum subarray is [4, -1, 2, 1] with sum 4 + (-1) + 2 + 1 = 6, but check if including more elements helps.

2. Step 2: Check if extending subarray increases sum

   Including the element before 4 is -3 (reduces sum), after 1 is -5 (reduces sum), so max sum is 6.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Max subarray sum = 6 [OK]

Hint: Find max sum of continuous elements [OK]

Common Mistakes:

• Counting non-continuous elements
• Miscomputing sums with negative numbers
• Assuming max element alone is answer

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

int maxCrossingSum(int arr[], int low, int mid, int high) {
    int left_sum = 0, sum = 0;
    for (int i = mid; i >= low; i--) {
        sum += arr[i];
        if (sum > left_sum)
            left_sum = sum;
    }
    int right_sum = 0;
    sum = 0;
    for (int i = mid + 1; i <= high; i++) {
        sum += arr[i];
        if (sum > right_sum)
            right_sum = sum;
    }
    return left_sum + right_sum;
}

medium

A. left_sum and right_sum should be initialized to INT_MIN, not 0

B. The loops should start from low and high, not mid

C. sum variable should not be reset between loops

D. Return statement should subtract left_sum from right_sum

Solution

1. Step 1: Understand initialization of sums

   Initializing left_sum and right_sum to 0 causes errors if all numbers are negative, as max sum could be less than 0.

2. Step 2: Correct initialization

   They should be initialized to the smallest integer (INT_MIN) to correctly track max sums even if negative.

3. Final Answer:

   left_sum and right_sum should be initialized to INT_MIN, not 0 -> Option A

4. Quick Check:

   Initialize max sums to INT_MIN to handle negatives [OK]

Hint: Use INT_MIN for max sums to handle negative arrays [OK]

Common Mistakes:

• Initializing max sums to zero causes wrong results
• Not resetting sum variable properly
• Incorrect loop ranges

5. Given an array arr = [-1, -2, -3, -4], what will the divide and conquer max subarray function return and why?

hard

A. 0 because empty subarray sum is considered

B. -1 because the max subarray is the single largest element

C. -10 because sum of all elements is max

D. -4 because last element is max

Solution

1. Step 1: Analyze array with all negative numbers

   All elements are negative, so the max subarray is the one with the least negative value (largest number).

2. Step 2: Identify max element

   The largest element is -1, so max subarray sum is -1 (single element subarray).

3. Final Answer:

   -1 because the max subarray is the single largest element -> Option B

4. Quick Check:

   Max subarray in negatives = max single element [OK]

Hint: Max subarray in all negatives is max single element [OK]

Common Mistakes:

• Assuming sum of all negatives is max
• Considering empty subarray sum as zero incorrectly
• Picking last element without comparison