Bird
Raised Fist0
DSA Javaprogramming~5 mins

Find Maximum Subarray Divide and Conquer in DSA Java - 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, we ask: How does the divide and conquer method scale with input size?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public int maxSubArray(int[] nums, int left, int right) {
    if (left == right) return nums[left];
    int mid = (left + right) / 2;
    int leftMax = maxSubArray(nums, left, mid);
    int rightMax = maxSubArray(nums, mid + 1, right);
    int crossMax = maxCrossingSubArray(nums, left, mid, right);
    return Math.max(Math.max(leftMax, rightMax), crossMax);
}

private int maxCrossingSubArray(int[] nums, int left, int mid, int right) {
    int leftSum = Integer.MIN_VALUE, sum = 0;
    for (int i = mid; i >= left; i--) {
        sum += nums[i];
        if (sum > leftSum) leftSum = sum;
    }
    int rightSum = Integer.MIN_VALUE;
    sum = 0;
    for (int i = mid + 1; i <= right; i++) {
        sum += nums[i];
        if (sum > rightSum) rightSum = sum;
    }
    return leftSum + rightSum;
}

This code finds the maximum sum of a contiguous subarray using divide and conquer.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

  • Primary operation: Recursive calls splitting the array into halves.
  • How many times: Each call splits the array until single elements remain, about log n levels.
  • Additional operation: The maxCrossingSubArray scans parts of the array linearly at each level.
  • Dominant operation: The linear scans in maxCrossingSubArray at each recursion level.
How Execution Grows With Input

At each level, the array is split into two halves, and the crossing sum is found by scanning parts of the array.

Input Size (n)Approx. Operations
10About 10 + 5 + 5 + ... ≈ 30 operations
100About 100 + 50 + 50 + ... ≈ 700 operations
1000About 1000 + 500 + 500 + ... ≈ 9000 operations

Pattern observation: The total work roughly doubles with each doubling of input size, growing a bit faster than linear but less than quadratic.

Final Time Complexity

Time Complexity: O(n log n)

This means the time grows a bit faster than the size of the input, multiplying by the logarithm of the input size.

Common Mistake

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

[OK] Correct: Although the array splits reduce the problem size, the crossing sum requires scanning parts of the array at each level, adding linear work per level, so total time is O(n log n), not just O(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 linear scan in maxCrossingSubArray with a constant-time operation? 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 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
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