Bird
Raised Fist0
DSA Cprogramming~5 mins

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

Choose your learning style10 modes available
LearnWhyDeepVisualTryChallengeProjectRecallTime
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 array gets bigger.

Specifically, how the divide and conquer method affects the work done.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.


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

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 (left_max > right_max) ? (left_max > cross_max ? left_max : cross_max) : (right_max > cross_max ? right_max : cross_max);
}

This code finds the maximum sum of a subarray using divide and conquer by splitting the array and combining results.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

  • Primary operation: Recursive calls splitting the array into halves.
  • How many times: Each level splits the array into two parts, so recursion depth is about log n.
  • Secondary operation: The maxCrossingSum function loops over parts of the array crossing the middle.
  • How many times: At each recursion level, maxCrossingSum scans parts of the array once, totaling n work per level.
How Execution Grows With Input

At each level, the total work scanning the array is about n, and the number of levels is about log n.

Input Size (n)Approx. Operations
10About 10 * 4 = 40
100About 100 * 7 = 700
1000About 1000 * 10 = 10,000

Pattern observation: Operations grow roughly by n times log n, meaning work grows faster than linear but slower than quadratic.

Final Time Complexity

Time Complexity: O(n log n)

This means the time needed grows a bit faster than the size of the input, but not as fast as checking every pair.

Common Mistake

[X] Wrong: "Since the array is split in half each time, the time complexity is O(log n)."

[OK] Correct: Although the array splits reduce the problem size, the crossing sum loops over parts of the array at each level, adding up to n work per level, so total work is more than just log n.

Interview Connect

Understanding this divide and conquer approach helps you see how breaking problems down and combining results affects performance, a key skill in many coding challenges.

Self-Check

"What if we replaced the maxCrossingSum function with a method that scans the entire array each time? How would the time complexity change?"

Practice

(1/5)
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
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard