In this article, we will learn about how to find the maximum subarray sum using the binary search approach. So, what is it? Given an array, it is the maximum sum obtained by adding the contiguous array elements. Let’s examine the example below to better understand this concept.
Array = [-2, 1, 4, -5, -1, 4, -1, 5] Maximum subarray sum = 8
The brute force approach to this problem is very inefficient, i.e., it has a time complexity of O(n2). We can find a better solution using the binary search approach. It will have a time complexity of O(nlogn).
- Divide the array into two halves using the midpoint
- Find the maximum subarray sum in the left half and the right half, recursively. One thing to notice here is that the MS can also include some elements from the left and some from the right, i.e., subarray crossing the midpoint. Therefore, we need to handle this case as well.
- To find the maximum crossing subarray sum, we define another method that takes an array, starting index of the left subarray l, midpoint
m, and the last index of the right subarray
r. It finds the maximum possible sum starting from the midpoint to the beginning of the left subarray, iteratively. It also calculates the largest sum starting after the midpoint till the end of the right subarray. Then, it adds both and returns the result.
- Return the maximum of the left subarray sum, right subarray sum, and crossing sum.
Consider the image below to understand this concept.
import math def findCrossingSum(arr, l, m, r): #find the maximum possible sum from mid to the beginning of the left part l_sum = 0 max_left= -math.inf for i in range(m, l-1, -1): l_sum += arr[i] if l_sum > max_left: max_left = l_sum #find the maximum possible sum after mid to the end of the right part r_sum = 0 max_right = -math.inf for i in range(m+1, r+1): r_sum += arr[i] if r_sum > max_right: max_right = r_sum return max_right+max_left def maxSubArraySum(arr, l, r): if l > r: return None if (r==l): return arr[l] m = l + (r-l)//2 left_sum = maxSubArraySum(arr, l, m) #MS in the left half right_sum = maxSubArraySum(arr, m+1, r) #MS in the right half cross_sum = findCrossingSum(arr, l, m, r) #MS crossing the find mid point return max(left_sum, right_sum, cross_sum) array = [-2, 1, 4, -5, -1, 4, -1, 5] max_sum = maxSubArraySum(array, 0, len(array)-1) print("Maximum subarray sum:", max_sum)
Maximum subarray sum: 8