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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Maximum Subarray Sum Using Divide and Conquer

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

DSA C#

using System;

class Program {
    static int MaxCrossingSum(int[] arr, int left, int mid, int right) {
        int sum = 0;
        int left_sum = int.MinValue;
        for (int i = mid; i >= left; i--) {
            sum += arr[i];
            if (sum > left_sum) left_sum = sum;
        }
        sum = 0;
        int right_sum = int.MinValue;
        for (int i = mid + 1; i <= right; i++) {
            sum += arr[i];
            if (sum > right_sum) right_sum = sum;
        }
        return left_sum + right_sum;
    }

    static int MaxSubArraySum(int[] arr, int left, int right) {
        if (left == right) return arr[left];
        int mid = (left + right) / 2;
        int left_max = MaxSubArraySum(arr, left, mid);
        int right_max = MaxSubArraySum(arr, mid + 1, right);
        int cross_max = MaxCrossingSum(arr, left, mid, right);
        return Math.Max(Math.Max(left_max, right_max), cross_max);
    }

    static void Main() {
        int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        int max_sum = MaxSubArraySum(arr, 0, arr.Length - 1);
        Console.WriteLine(max_sum);
    }
}

A 4

B 6

C 5

D 7

💡 Hint

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

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

❓ Predict Output

intermediate

Maximum Subarray Sum for All Negative Numbers

What is the output of this C# code when the input array contains all negative numbers?

DSA C#

using System;

class Program {
    static int MaxCrossingSum(int[] arr, int left, int mid, int right) {
        int sum = 0;
        int left_sum = int.MinValue;
        for (int i = mid; i >= left; i--) {
            sum += arr[i];
            if (sum > left_sum) left_sum = sum;
        }
        sum = 0;
        int right_sum = int.MinValue;
        for (int i = mid + 1; i <= right; i++) {
            sum += arr[i];
            if (sum > right_sum) right_sum = sum;
        }
        return left_sum + right_sum;
    }

    static int MaxSubArraySum(int[] arr, int left, int right) {
        if (left == right) return arr[left];
        int mid = (left + right) / 2;
        int left_max = MaxSubArraySum(arr, left, mid);
        int right_max = MaxSubArraySum(arr, mid + 1, right);
        int cross_max = MaxCrossingSum(arr, left, mid, right);
        return Math.Max(Math.Max(left_max, right_max), cross_max);
    }

    static void Main() {
        int[] arr = {-8, -3, -6, -2, -5, -4};
        int max_sum = MaxSubArraySum(arr, 0, arr.Length - 1);
        Console.WriteLine(max_sum);
    }
}

A -5

B -3

C -4

D -2

💡 Hint

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

The largest element is -2, so the maximum subarray sum is -2.

🔧 Debug

advanced

Identify the Bug in MaxCrossingSum Implementation

Which option correctly identifies the bug in this MaxCrossingSum method?

DSA C#

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

A sum should be reset to int.MinValue before the second loop

B The for loops should run from left to mid and mid+1 to right respectively

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

D The return statement should return Math.Max(left_sum, right_sum) instead of sum

💡 Hint

Consider what happens if all numbers are negative.

Initializing left_sum and right_sum to 0 causes the function to ignore negative sums, which is wrong if all numbers are negative.

🧠 Conceptual

advanced

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?

A O(n log n)

B O(n^2)

C O(n)

D O(log n)

💡 Hint

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

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

🚀 Application

expert

Find Maximum Subarray Indices Using Divide and Conquer

Which option correctly modifies the divide and conquer approach to return the start and end indices of the maximum subarray along with the sum?

DSA C#

static (int maxSum, int start, int end) MaxCrossingSum(int[] arr, int left, int mid, int right) {
    int sum = 0;
    int left_sum = int.MinValue;
    int max_left = mid;
    for (int i = mid; i >= left; i--) {
        sum += arr[i];
        if (sum > left_sum) {
            left_sum = sum;
            max_left = i;
        }
    }
    sum = 0;
    int right_sum = int.MinValue;
    int max_right = mid + 1;
    for (int i = mid + 1; i <= right; i++) {
        sum += arr[i];
        if (sum > right_sum) {
            right_sum = sum;
            max_right = i;
        }
    }
    return (left_sum + right_sum, max_left, max_right);
}

static (int maxSum, int start, int end) MaxSubArraySum(int[] arr, int left, int right) {
    if (left == right) return (arr[left], left, right);
    int mid = (left + right) / 2;
    var left_result = MaxSubArraySum(arr, left, mid);
    var right_result = MaxSubArraySum(arr, mid + 1, right);
    var cross_result = MaxCrossingSum(arr, left, mid, right);
    if (left_result.maxSum >= right_result.maxSum && left_result.maxSum >= cross_result.maxSum) return left_result;
    else if (right_result.maxSum >= left_result.maxSum && right_result.maxSum >= cross_result.maxSum) return right_result;
    else return cross_result;
}

static void Main() {
    int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    var result = MaxSubArraySum(arr, 0, arr.Length - 1);
    Console.WriteLine($"Sum: {result.maxSum}, Start: {result.start}, End: {result.end}");
}

A Sum: 6, Start: 3, End: 6

B Sum: 5, Start: 3, End: 7

C Sum: 6, Start: 2, End: 5

D Sum: 7, Start: 2, End: 6

💡 Hint

Track indices when calculating left and right sums crossing the midpoint.

The maximum subarray is [4, -1, 2, 1] from index 3 to 6 with sum 6.

Practice

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

easy

A. Calculate sum of all subarrays and pick the maximum

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

C. Use a sliding window to find the max sum subarray in one pass

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

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 subproblems

   Find max subarray in left half, right half, and crossing the middle, then take the maximum of these three.

3. Final Answer:

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

4. Quick Check:

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

Hint: Divide array, conquer halves, combine max sums [OK]

Common Mistakes:

• Thinking sorting helps find max subarray sum
• Using brute force sum of all subarrays
• Confusing divide and conquer with sliding window

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

easy

A. If the array length is 0, return 0

B. If the array length is 1, return the single element

C. If the array length is 2, return the sum of both elements

D. If the array length is 1, return 0

Solution

1. Step 1: Identify base case for recursion

   When the array has only one element, that element itself is the max subarray sum.

2. Step 2: Return the single element value

   Return the value of that single element as the maximum sum.

3. Final Answer:

   Return single element when array length is 1 -> Option B

4. Quick Check:

   Base case = single element value [OK]

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

Common Mistakes:

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

3. What will be 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 maxSum = FindMaxSubarray(arr, 0, arr.Length - 1);
Console.WriteLine(maxSum);

int FindMaxSubarray(int[] a, int left, int right) {
    if (left == right) return a[left];
    int mid = (left + right) / 2;
    int leftMax = FindMaxSubarray(a, left, mid);
    int rightMax = FindMaxSubarray(a, mid + 1, right);
    int crossMax = FindMaxCrossingSubarray(a, left, mid, right);
    return Math.Max(Math.Max(leftMax, rightMax), crossMax);
}

int FindMaxCrossingSubarray(int[] a, int left, int mid, int right) {
    int leftSum = int.MinValue, sum = 0;
    for (int i = mid; i >= left; i--) {
        sum += a[i];
        if (sum > leftSum) leftSum = sum;
    }
    int rightSum = int.MinValue;
    sum = 0;
    for (int j = mid + 1; j <= right; j++) {
        sum += a[j];
        if (sum > rightSum) rightSum = sum;
    }
    return leftSum + rightSum;
}

medium

A. 6

B. 7

C. 5

D. 4

Solution

1. Step 1: Identify the maximum subarray sum

   The array is [-2, 1, -3, 4, -1, 2, 1, -5, 4]. The subarray [4, -1, 2, 1] (indices 3-6) sums to 6, which is the maximum.

2. Step 2: Trace the code execution

   Split at mid=4: leftMax (0-4) = 4, rightMax (5-8) = 4, crossMax = 6 ([3-6]). Returns Math.Max(4, 4, 6) = 6.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   max(leftMax=4, rightMax=4, crossMax=6) = 6 [OK]

Hint: Trace subarray sums carefully to find max [OK]

Common Mistakes:

• Miscomputing crossing sum
• Confusing max subarray with max element
• Ignoring negative numbers impact

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

int FindMaxCrossingSubarray(int[] a, int left, int mid, int right) {
    int leftSum = 0, sum = 0;
    for (int i = mid; i >= left; i--) {
        sum += a[i];
        if (sum > leftSum) leftSum = sum;
    }
    int rightSum = 0;
    sum = 0;
    for (int j = mid + 1; j <= right; j++) {
        sum += a[j];
        if (sum > rightSum) rightSum = sum;
    }
    return leftSum + rightSum;
}

medium

A. leftSum and rightSum should be initialized to int.MinValue, not 0

B. The loops should run from left to mid and mid+1 to right respectively

C. sum variable should not be reset between loops

D. The function should return max of leftSum and rightSum, not their sum

Solution

1. Step 1: Check initialization of leftSum and rightSum

   They are initialized to 0, which fails if all numbers are negative because max sum could be less than 0.

2. Step 2: Correct initialization to int.MinValue

   Initialize leftSum and rightSum to int.MinValue to correctly track max sums even if negative.

3. Final Answer:

   Initialize leftSum and rightSum to int.MinValue -> Option A

4. Quick Check:

   Init max sums to int.MinValue to handle negatives [OK]

Hint: Init max sums to int.MinValue to handle negatives [OK]

Common Mistakes:

• Initializing max sums to 0 causing wrong results
• Resetting sum incorrectly between loops
• Returning sum instead of max in crossing function

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

hard

A. -4

B. 0

C. -1

D. -10

Solution

1. Step 1: Analyze array with all negative numbers

   All elements are negative, so max subarray is the single largest element.

2. Step 2: Identify largest element

   The largest element is -1, which is the max subarray sum.

3. Final Answer:

   -1 -> Option C

4. Quick Check:

   Max subarray in negatives = max element [OK]

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

Common Mistakes:

• Returning 0 instead of max negative element
• Summing all negatives incorrectly
• Assuming empty subarray sum is allowed