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).

Algorithm

1. Divide the array into two halves using the midpoint m.
2. 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.
3. 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.
4. Return the maximum of the left subarray sum, right subarray sum, and crossing sum.

Consider the image below to understand this concept.

Implementation

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)

Output

Maximum subarray sum: 8