Maximum Subarray Sum using Divide and Conquer

Problem Statement

In the “Maximum Subarray Sum using Divide and Conquer” problem we have given an array of both positive and negative integers. Write a program that will find the largest sum of the contiguous subarray.

Input Format

The first line containing an integer N.

Second-line containing an array of integer which containing N integers.

Output Format

Print an integer value that denotes the maximum sum subarray of the given array.

Constraints

• 1<=N<=10^5
• 1<=a[i]<=10^5

Example

5
-10 2 5 12 -5

19

Algorithm

Here we use Divide and Conquer approach. We can find the maximum subarray sum in O(nLogn) time. Following is the Divide and Conquer algorithm.

1. Divide the array into two parts.

2. Recursively find the maximum subarray sum for the left subarray.

3. Recursively find the maximum subarray sum for the right subarray.

4. Find the maximum subarray sum that crosses the midpoint.

5. Return the maximum of the above three sums.

Lines 2 and 3 are simple recursive calls. How to find the maximum subarray sum such that the subarray crosses the midpoint? We can easily find the crossing sum in linear time. The idea is simple, find the maximum sum starting from midpoint and ending at some point on the left of mid, then find the maximum sum starting from mid + 1 and ending with sum point on the right of mid + 1. Finally, combine the two and return.

Implementation

C++ Program for Maximum Subarray Sum using Divide and Conquer

#include <bits/stdc++.h>
using namespace std;

int cross_sum(int arr[], int l, int m, int h)
{
  int sum = 0;
  int left_sum = INT_MIN;
  for (int i = m; i >= l; i--) 
  {
    sum = sum + arr[i];
    if (sum > left_sum)
      left_sum = sum;
  }
  sum = 0;
  int right_sum = INT_MIN;
  for (int i = m + 1; i <= h; i++) 
  {
    sum = sum + arr[i];
    if (sum > right_sum)
      right_sum = sum;
  }
  return max(left_sum + right_sum, max(left_sum, right_sum));
}


int max_sum(int arr[], int l, int h)
{
  if(l==h)
  {
    return arr[l];
  }
  int m=(l+h)/2;
  return max(max_sum(arr, l, m), max(max_sum(arr, m + 1, h), cross_sum(arr, l, m, h)));
} 

int main()
{
  int n;
  cin>>n;
  int a[n];
  for(int i=0;i<n;i++)
  {
      cin>>a[i];
  }
  int sum = max_sum(a,0,n-1);
  cout<<sum<<endl;
  return 0;
}

Java Program for Maximum Subarray Sum using Divide and Conquer

import java.util.Scanner;
class sum
{
    public static int cross_sum(int arr[], int l, int m, int h)
    {
            int sum = 0;
            int left_sum = -1000000;
            for (int i = m; i >= l; i--) 
            {
                    sum = sum + arr[i];
                    if (sum > left_sum)
                            left_sum = sum;
            }
            sum = 0;
            int right_sum = -1000000;
            for (int i = m + 1; i <= h; i++) 
            {
                    sum = sum + arr[i];
                    if (sum > right_sum)
                            right_sum = sum;
            }
            return Math.max(left_sum + right_sum, Math.max(left_sum, right_sum));
    }
    public static int max_sum(int arr[], int l, int h) 
    {
        if(l==h)
  {
    return arr[l];
  }
  int m=(l+h)/2;
  return Math.max(max_sum(arr, l, m), Math.max(max_sum(arr, m + 1, h), cross_sum(arr, l, m, h)));
    }
    public static void main(String[] args)
    {
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int [n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int sum = max_sum(a,0,n-1);
        System.out.println(sum);
    }
}

7
10 5 -106 29 100 1000 -500

1129

Complexity Analysis for Maximum Subarray Sum using Divide and Conquer

Time Complexity

O(n*logn) where n is the size of the given array. Here we come up with this recurrence relation t(n) = 2*t(n/2)+θ(n). When we solve this recurrence relation then get the value of t(n) as n*logn.

Space Complexity

O(1) because we don’t use any auxiliary space at here.