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

Recall & Review

beginner

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

The array is split into two halves, the maximum subarray is found in the left half, right half, and the subarray crossing the middle. The overall maximum is the largest of these three.

intermediate

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

We 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?

The time complexity is 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 Divide and Conquer approach better than the brute force method for maximum subarray?

Because it reduces the time complexity from O(n²) in brute force to O(n log n) by dividing the problem and combining results efficiently.

beginner

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

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 'crossing subarray' mean in the Divide and Conquer maximum subarray problem?

A A subarray that includes elements from both left and right halves crossing the middle

B A subarray only in the left half

C A subarray only in the right half

D A subarray with all negative numbers

The crossing subarray includes elements from both halves and crosses the middle point.

What is the base case for the Divide and Conquer maximum subarray algorithm?

A When the array has one element

B When the array is empty

C When the array has two elements

D When the array is sorted

The base case is when the array has only one element, which is the maximum subarray itself.

Which step takes linear time in the Divide and Conquer maximum subarray algorithm?

A Recursively solving left half

B Dividing the array into halves

C Finding the maximum crossing subarray

D Recursively solving right half

Finding the maximum crossing subarray requires scanning from the middle to left and right, which is linear time.

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

A O(n²)

B O(n log n)

C O(log n)

D O(n)

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

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

A Find maximum subarray in left half

B Find maximum subarray in right half

C Find maximum subarray crossing the middle

D Sort the array before processing

Sorting is not required for the maximum subarray problem in Divide and Conquer.

Explain how the Divide and Conquer approach finds the maximum subarray in an array.

Think about splitting and combining results.

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

Focus on sums on both sides of the middle.

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 max sum subarray in one pass

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

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

D. Calculate all possible subarrays and pick the one with the maximum sum

Solution

1. Step 1: Understand divide and conquer strategy

   The array is divided 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.

3. Final Answer:

   Split array, find max in left, right, crossing, then combine -> Option C

4. Quick Check:

   Divide and conquer = split and combine max sums [OK]

Hint: Divide array, solve halves, combine crossing max [OK]

Common Mistakes:

• Thinking sorting helps find max subarray sum
• Confusing divide and conquer with sliding window
• Ignoring subarrays crossing the middle

2. Which of the following is the correct base case for the recursive function in the divide and conquer approach to find the maximum subarray?

easy

A. When the array is empty, return 0

B. When the array has only one element, return that element

C. When the array has two elements, return their sum

D. When the array has more than one element, return the max of left and right

Solution

1. Step 1: Identify base case for recursion

   The recursion stops when the subarray has only one element.

2. Step 2: Return the single element as max subarray sum

   Since one element is the smallest subarray, return it directly.

3. Final Answer:

   Return single element when array size is one -> Option B

4. Quick Check:

   Base case = single element return [OK]

Hint: Base case: single element returns itself [OK]

Common Mistakes:

• Returning 0 for empty array instead of handling single element
• Using sum of two elements as base case
• Not defining a base case causing infinite recursion

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

int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
System.out.println(maxSubArray(arr, 0, arr.length - 1));

// Assume maxSubArray is correctly implemented divide and conquer method

medium

A. 4

B. 7

C. 5

D. 6

Solution

1. Step 1: Identify max subarray in given array

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

2. Step 2: Check if any larger sum exists

   Adding the next element -5 or 4 does not increase sum beyond 6, but including the last 4 gives total 5 for subarray [4, -1, 2, 1, -5, 4]?

3. Step 3: Correct max subarray is [4, -1, 2, 1] with sum 6

   Actually, the max sum is 6, not 5.

4. Final Answer:

   6 -> Option D

5. Quick Check:

   Max subarray sum = 6 [OK]

Hint: Find max sum subarray by checking sums around middle [OK]

Common Mistakes:

• Choosing sum including negative elements that reduce total
• Miscounting elements in max subarray
• Confusing max sum with max element

4. Identify the error in this divide and conquer code snippet for max subarray sum:

int maxCrossingSum(int[] arr, int left, int mid, int right) {
    int sum = 0, left_sum = Integer.MIN_VALUE;
    for (int i = mid; i >= left; i--) {
        sum += arr[i];
        if (sum > left_sum) left_sum = sum;
    }
    sum = 0;
    int right_sum = Integer.MIN_VALUE;
    for (int i = mid + 1; i <= right; i++) {
        sum += arr[i];
        if (sum > right_sum) right_sum = sum;
    }
    return left_sum + right_sum;
}

medium

A. No error, code correctly finds max crossing sum

B. Should initialize sum to Integer.MIN_VALUE instead of 0

C. Return statement should be max of left_sum and right_sum, not sum

D. Loop ranges are incorrect; should start from left+1 and mid-1

Solution

1. Step 1: Analyze loops for left and right sums

   Loops correctly accumulate sums from mid to left and mid+1 to right.

2. Step 2: Check return statement

   Returns sum of max left and right sums crossing mid, which is correct for crossing subarray.

3. Final Answer:

   No error, code correctly finds max crossing sum -> Option A

4. Quick Check:

   Crossing sum = left max + right max [OK]

Hint: Crossing sum = max left + max right sums around mid [OK]

Common Mistakes:

• Initializing sum to wrong value causing incorrect sums
• Returning max instead of sum of left and right max
• Incorrect loop boundaries skipping elements

5. Given the array int[] arr = {-1, -2, -3, -4}, what will the divide and conquer algorithm return as the maximum subarray sum?

hard

A. -1

B. -10

C. 0

D. -4

Solution

1. Step 1: Understand max subarray with all negative numbers

   When all numbers are negative, max subarray is the single largest (least negative) element.

2. Step 2: Identify largest element in array

   Largest element is -1, so max subarray sum is -1.

3. Final Answer:

   -1 -> Option A

4. Quick Check:

   Max subarray sum with negatives = max element [OK]

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

Common Mistakes:

• Summing all negatives instead of picking max element
• Returning zero incorrectly assuming empty subarray
• Confusing max subarray sum with min element