Find Maximum Subarray Divide and Conquer in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Divide and Conquer Maximum Subarray Sum

What is the output of the following C code that finds the maximum subarray sum using divide and conquer?

DSA C

int max(int a, int b) { return (a > b) ? a : b; }

int maxCrossingSum(int arr[], int l, int m, int h) {
    int sum = 0;
    int left_sum = -2147483648;
    for (int i = m; i >= l; i--) {
        sum += arr[i];
        if (sum > left_sum) left_sum = sum;
    }
    sum = 0;
    int right_sum = -2147483648;
    for (int i = m + 1; i <= h; i++) {
        sum += arr[i];
        if (sum > right_sum) right_sum = sum;
    }
    return left_sum + right_sum;
}

int maxSubArraySum(int arr[], int l, int h) {
    if (l == h) return arr[l];
    int m = (l + h) / 2;
    int left_max = maxSubArraySum(arr, l, m);
    int right_max = maxSubArraySum(arr, m + 1, h);
    int cross_max = maxCrossingSum(arr, l, m, h);
    return max(max(left_max, right_max), cross_max);
}

#include <stdio.h>
int main() {
    int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    int max_sum = maxSubArraySum(arr, 0, n - 1);
    printf("%d", max_sum);
    return 0;
}

A 6

B 7

C 5

D 4

💡 Hint

Think about the subarray with the largest sum in the array.

The maximum subarray is [4, -1, 2, 1] which sums to 6.

🧠 Conceptual

intermediate

Key Idea Behind Divide and Conquer for Maximum Subarray

Which statement best describes the key idea behind the divide and conquer approach to find the maximum subarray?

A Sort the array and pick the largest element as the maximum subarray sum.

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

C Divide the array into two halves, find maximum subarray in left, right, and crossing middle, then take the maximum.

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

💡 Hint

Think about how the problem is split into smaller parts.

Divide and conquer splits the array into two halves and considers three cases: max subarray in left half, right half, or crossing the middle.

🔧 Debug

advanced

Identify the Bug in maxCrossingSum Function

What is the bug in this maxCrossingSum function snippet?

DSA C

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

A left_sum and right_sum initialized to 0 cause incorrect results when all numbers are negative.

B The loops should run from l to m and m+1 to h instead of backwards.

C sum variable should be declared inside the loops to reset automatically.

D The function should return max(left_sum, right_sum) instead of their sum.

💡 Hint

Consider what happens if all elements are negative.

Initializing left_sum and right_sum to 0 causes the function to ignore negative sums, leading to wrong max crossing sums when all elements are negative.

❓ Predict Output

advanced

Output of maxSubArraySum on All Negative Array

What is the output of the following code snippet?

DSA C

int arr[] = {-8, -3, -6, -2, -5, -4};
int n = sizeof(arr) / sizeof(arr[0]);
int max_sum = maxSubArraySum(arr, 0, n - 1);
printf("%d", max_sum);

A -8

B -3

C 0

D -2

💡 Hint

The maximum subarray in all negative numbers is the least negative single element.

The maximum subarray is [-2] with sum -2, which is the largest among all negative elements.

🚀 Application

expert

Time Complexity of Divide and Conquer Maximum Subarray

What is the time complexity of the divide and conquer algorithm for finding the maximum subarray sum for an array of size n?

A O(n^2)

B O(n log n)

C O(n)

D O(log n)

💡 Hint

Consider the recurrence relation T(n) = 2T(n/2) + O(n).

The algorithm divides the problem into two halves and combines results in linear time, leading to O(n log n) complexity.