Finding Maximum-Subarray Sum using Divide-and-Conquer Approach : Datastructures and Algorithms

In my previous blog, I wrote about Divide-and-Conquer Stragey of Algorithm Designing. Finding maximum subarray sum problem is one of the application of this strategy.

Problem

Lets first understand the problem:

• You are given an One-dimensional array that may contain both positive and negative integers.
• You’ve to find the sum of the continous subarray of numbers which has the largest sum.

Example: If you’re given an array [-2, 1, -3, 4, -1, 2, 1, -5, 4]. The maximum subarray sum is 6, achieved by the subarray [4, -1, 2, 1].

Algorithm / Solution

We can solve this problem efficiently using the Divide and Conquer algorithm.

• Divide: Divide the array recursively into two halves until reaching subarrays with a single element.
• Conquer: Find the maximum subarray sum within each subarray (base case).
• Combine: Calculate three possible maximum sums:
  • Maximum subarray sum in the left half (left_max_sum).
  • Maximum subarray sum in the right half (right_max_sum).
  • Maximum subarray sum that crosses the middle element (cross_max_sum). Finding cross_max_sum involves iterating through the left half to find the maximum sum ending at the middle and iterating through the right half to find the maximum sum starting from the middle element (finding both the maximum prefix sum on the left and maximum suffix sum on the right).
  • Return the maximum of these three sums (left_max_sum, right_max_sum, cross_max_sum).

Sample Code

def max_subarray_sum(arr, low, high):
  if low == high:
    return arr[low]

  mid = (low + high)
  left_sum = max_subarray_sum(arr, low, mid)
  right_sum = max_subarray_sum(arr, mid + 1, high)

  # Find maximum sum crossing the middle
  left_max_sum = float('-inf')
  curr_sum = 0
  for i in range(mid, low - 1, -1):
    curr_sum += arr[i]
    left_max_sum = max(left_max_sum, curr_sum)

  right_max_sum = float('-inf')
  curr_sum = 0
  for i in range(mid + 1, high + 1):
    curr_sum += arr[i]
    right_max_sum = max(right_max_sum, curr_sum)

  cross_sum = left_max_sum + right_max_sum

  # Return maximum of left, right, and crossing sums
  return max(left_sum, right_sum, cross_sum)

# Example usage
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
max_sum = max_subarray_sum(arr, 0, len(arr) - 1)
print("Maximum subarray sum:", max_sum)

Analysis

Efficiency:

• Time Complexity: O(n log n)
  • Recursively breaking down the problem halves the size of the array with each step (log n).
  • Solving the subproblems takes linear time (n) for each half.
• Space Complexity: O(log n)
  • Due to the recursion stack used during the divide and conquer process.

Breakdown of Time Complexity:

• Each recursive call solves a subproblem half the size of the previous one.
• The number of recursive calls is roughly logarithmic to the array size (log n).
• Within each call, iterating through the subarrays for finding cross_max_sum takes linear time (n) for each half.
• Combining these factors results in O(n log n) overall complexity.

Comparison:

• This Divide and Conquer approach is more efficient than the naive O(n^2) solution that checks every possible subarray.

Conclusion

The Divide and Conquer method provides an efficient solution for finding the maximum subarray sum, achieving a time complexity of O(n log n) compared to the O(n^2) complexity of the naive approach. This makes it a valuable technique for dealing with problems that can be broken down into smaller subproblems.