BlogsDope image BlogsDope

Maximum Subarray Sum Using Divide and Conquer

Consider visiting the divide and conquer post for the basics of divide and conquer.

The problem of maximum subarray sum is basically finding the part of an array whose elements has the largest sum. If all the elements in an array are positive then it is easy, find the sum of all the elements of the array and it has the largest sum over any other subarrays you can make out from that array.

maximum subarray sum with positive elements

But the problem gets more interesting when some of the elements are negative then the subarray whose sum of the elements is largest over the sum of the elements of any other subarrays of that element can lie anywhere in the array.

maximum subarray sum with negative elements

Brute Force vs Divide and Conquer


The Brute Force technique to solve the problem is simple. Just iterate through every element of the array and check the sum of all the subarrays that can be made starting from that element i.e., check all the subarrays and this can be done in nC2 ways i.e., choosing two different elements of the array to make a subarray.

Thus, the brute force technique is of Θ(n2) time. However,  we can solve this in Θ(nlog(n)) time using divide and conquer.

Coding Up Maximum Subarray Sum Using Divide and Conquer


As we know that the divide and conquer solves a problem by breaking into subproblems, so let's first break an array into two parts. Now, the subarray with maximum sum can either lie entirely in the left subarray or entirely in the right subarray or in a subarray consisting both i.e., crossing the middle element.

maximum sum subarray

The first two cases where the subarray is entirely on right or on the left are actually the smaller instances of the original problem. So, we can solve them recursively by calling the function to calculate the maximum sum subarray on both the parts.

max_sum_subarray(array, low, high)
{
  if (high == low) // only one element in an array
  {
    return array[high]
  }
  mid = (high+low)/2

  max_sum_subarray(array, low, mid)
  max_sum_subarray(array, mid+1, high)
}

We are making max_sum_subarray is a function to calculate the maximum sum of the subarray in an array. Here, we are calling the function max_sum_subarray for both the left and the right subarrays i.e., recursively checking the left and the right subarrays for the maximum sum subarray.

Now, we have to handle the third case i.e., when the subarray with the maximum sum contains both the right and the left subarrays (containing the middle element). At a glance, this could look like a smaller instance of the original problem also but it is not because it contains a restriction that the subarray must contain the middle element and thus makes our problem much more narrow and less time taking.

So, we will now make a function called max_crossing_subarray to calculate the maximum sum of the subarray crossing the middle element and then call it inside the max_sum_subarray function.

max_sum_subarray(array, low, high)
{
  if (high == low) // only one element in an array
  {
    return array[high];
  }

  mid = (high+low)/2;

  maximum_sum_left_subarray = max_sum_subarray(array, low, mid)
  maximum_sum_right_subarray = max_sum_subarray(array, mid+1, high)
  maximum_sum_crossing_subarray = max_crossing_subarray(array, low, mid, high);

  // returning the maximum among the above three numbers
  return maximum(maximum_sum_left_subarray, maximum_sum_right_subarray, maximum_sum_crossing_subarray);
}

Here, we are covering all three cases mentioned above to and then just returning the maximum of these three. Now, let's write the max_crossing_subarray function.

The max_crossing_subarray function is simple, we just have to iterate over the right and the left sides of the middle element and find the maximum sum.

maximum crossing sum subarray

max_crossing_subarray(int ar[], int low, int mid, int high)
{

  left_sum = -infinity
  sum = 0
  for (i=mid downto low)
  {
    sum = sum+ar[i]
    if (sum>left_sum)
      left_sum = sum
  }

  right_sum = -infinity;
  sum = 0

  for (i=mid+1 to high)
  {
    sum=sum+ar[i]
    if (sum>right_sum)
      right_sum = sum
  }

  return (left_sum+right_sum)
}

Here, our first loop is iterating from the middle element to the lowest element of the left subarray to find the maximum sum and similarly the second loop is iterating from the middle+1 element to the highest element of the subarray to calculate the maximum sum of the subarray on the right side. And finally, we are returning summing both of them and returning the sum which is calculated from the subarray crossing the middle element.

C

#include <stdio.h>

// function to return maximum number among three numbers
int maximum(int a, int b, int c)
{
  if (a>=b && a>=c)
    return a;
  else if (b>=a && b>=c)
    return b;
  return c;
}

// function to find maximum sum of subarray crossing the middle element
int max_crossing_subarray(int ar[], int low, int mid, int high)
{
  /*
    Initial left_sum should be -infinity.
    One can also use INT_MIN from limits.h
  */
  int left_sum = -1000000;
  int sum = 0;
  int i;

  /*
    iterating from middle
    element to the lowest element
    to find the maximum sum of the left
    subarray containing the middle
    element also.
  */
  for (i=mid; i>=low; i--)
  {
    sum = sum+ar[i];
    if (sum>left_sum)
      left_sum = sum;
  }

  /*
    Similarly, finding the maximum
    sum of right subarray containing
    the adjacent right element to the
    middle element.
  */
  int right_sum = -1000000;
  sum = 0;

  for (i=mid+1; i<=high; i++)
  {
    sum=sum+ar[i];
    if (sum>right_sum)
      right_sum = sum;
  }

  /*
    returning the maximum sum of the subarray
    containing the middle element.
  */
  return (left_sum+right_sum);
}

// function to calculate the maximum subarray sum
int max_sum_subarray(int ar[], int low, int high)
{
  if (high == low) // only one element in an array
  {
    return ar[high];
  }

  // middle element of the array
  int mid = (high+low)/2;

  // maximum sum in the left subarray
  int maximum_sum_left_subarray = max_sum_subarray(ar, low, mid);
  // maximum sum in the right subarray
  int maximum_sum_right_subarray = max_sum_subarray(ar, mid+1, high);
  // maximum sum in the array containing the middle element
  int maximum_sum_crossing_subarray = max_crossing_subarray(ar, low, mid, high);

  // returning the maximum among the above three numbers
  return maximum(maximum_sum_left_subarray, maximum_sum_right_subarray, maximum_sum_crossing_subarray);
}

int main()
{
  int a[] = {3, -1, -1, 10, -3, -2, 4};
  printf("%d\n", max_sum_subarray(a, 0, 6));
  return 0;
}

Python

# function to return maximum number among three numbers
def maximum(a, b, c):
  if (a>=b and a>=c):
    return a
  elif (b>=a and b>=c):
    return b
  return c

# function to find maximum sum of subarray crossing the middle element
def max_crossing_subarray(ar, low, mid, high):
  '''
    Initial left_sum should be -infinity.
  '''
  left_sum = -1000000
  sum = 0

  '''
    iterating from middle
    element to the lowest element
    to find the maximum sum of the left
    subarray containing the middle
    element also.
  '''
  for i in range(mid, low-1, -1):
    sum = sum+ar[i]
    if (sum>left_sum):
      left_sum = sum

  '''
    Similarly, finding the maximum
    sum of right subarray containing
    the adjacent right element to the
    middle element.
  '''
  right_sum = -1000000
  sum = 0

  for i in range(mid+1, high+1):
    sum = sum+ar[i]
    if (sum>right_sum):
      right_sum = sum

  '''
    returning the maximum sum of the subarray
    containing the middle element.
  '''
  return left_sum+right_sum

# function to calculate the maximum subarray sum
def max_sum_subarray(ar, low, high):
  if (high == low): # only one element in an array
    return ar[high]

  # middle element of the array
  mid = (high+low)//2

  # maximum sum in the left subarray
  maximum_sum_left_subarray = max_sum_subarray(ar, low, mid)
  # maximum sum in the right subarray
  maximum_sum_right_subarray = max_sum_subarray(ar, mid+1, high)
  # maximum sum in the array containing the middle element
  maximum_sum_crossing_subarray = max_crossing_subarray(ar, low, mid, high)

  # returning the maximum among the above three numbers
  return maximum(maximum_sum_left_subarray, maximum_sum_right_subarray, maximum_sum_crossing_subarray)

a = [3, -1, -1, 10, -3, -2, 4]
print(max_sum_subarray(a, 0, 6))

Java

class MaxSubarray {

  // function to return maximum number among three numbers
  static int maximum(int a, int b, int c)
  {
    if (a>=b && a>=c)
      return a;
    else if (b>=a && b>=c)
      return b;
    return c;
  }

  // function to find maximum sum of subarray crossing the middle element
  static int maxCrossingSubarray(int ar[], int low, int mid, int high)
  {
    /*
      Initial leftSum should be -infinity.
    */
    int leftSum = Integer.MIN_VALUE;
    int sum = 0;
    int i;

    /*
      iterating from middle
      element to the lowest element
      to find the maximum sum of the left
      subarray containing the middle
      element also.
    */
    for (i=mid; i>=low; i--)
    {
      sum = sum+ar[i];
      if (sum>leftSum)
        leftSum = sum;
    }

    /*
      Similarly, finding the maximum
      sum of right subarray containing
      the adjacent right element to the
      middle element.
    */
    int rightSum = Integer.MIN_VALUE;
    sum = 0;

    for (i=mid+1; i<=high; i++)
    {
      sum=sum+ar[i];
      if (sum>rightSum)
        rightSum = sum;
    }

    /*
      returning the maximum sum of the subarray
      containing the middle element.
    */
    return (leftSum+rightSum);
  }

  // function to calculate the maximum subarray sum
  static int maxSumSubarray(int ar[], int low, int high)
  {
    if (high == low) // only one element in an array
    {
      return ar[high];
    }

    // middle element of the array
    int mid = (high+low)/2;

    // maximum sum in the left subarray
    int maximumSumLeftSubarray = maxSumSubarray(ar, low, mid);
    // maximum sum in the right subarray
    int maximumSumRightSubarray = maxSumSubarray(ar, mid+1, high);
    // maximum sum in the array containing the middle element
    int maximumSumCrossingSubarray = maxCrossingSubarray(ar, low, mid, high);

    // returning the maximum among the above three numbers
    return maximum(maximumSumLeftSubarray, maximumSumRightSubarray, maximumSumCrossingSubarray);
  }

  public static void main(String[] args) {
    int a[] = {3, -1, -1, 10, -3, -2, 4};
    System.out.println(maxSumSubarray(a, 0, 6));
  }
}

 


Liked the post?
Developer and founder of CodesDope.
Editor's Picks
0 COMMENT

Please login to view or add comment(s).