Maximum Subarray Sum using Divide and Conquer

Given an array of both positive and negative integers, this function will find the largest sum of contiguous subarray.

Example

INPUT:
arr[] = {3, -4, 6, 2, -1 }
OUTPUT:
8
subarray is {6, 2}

Time Complexity: O(nlogn)

Algorithm

1. Divide the array into two halves

2. Recursively find the maximum subarray sum for left subarray

3. Recursively find the maximum subarray sum for right subarray

4. Find the maximum subarray sum that crosses the midpoint

5. return the maximum of above three sums

C++ Program

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

int max(int a, int b)
{
	if (a>b)
	{
		return a;
	}
	else
	{
		return b;
	}
}
//Is a recursive method, which returns maximum sum subarray
int maxSubArraySum(int arr[], int low, int high)
{
	//
	if (low == high)
	{
		return arr[low];
	}
	int mid = (low+high)/2;
	//recursivley find left subarray
	int leftsubarray = maxSubArraySum(arr, low, mid);
	//recursively finding right subarray
	int rightsubarray = maxSubArraySum(arr, mid+1, high);
	int left_sum  = INT_MIN, right_sum = INT_MIN;
	int sum =0;
	//Finding the left sum
	for (int i = mid; i <high ; ++i)
	{
		sum = sum + arr[i];
		right_sum = max(right_sum, sum);
	}
	sum =0;
	//Finding the right sum
	for (int i = low; i < mid; ++i)
	{
		sum = sum + arr[i];
		left_sum = max(left_sum, sum);
	}
	int ans = max(leftsubarray,rightsubarray);//maximum of left and right subarray
	return max(ans,left_sum+right_sum);//maximum of ans and subarray paasing through mid

}
int main()
{
	int arr[]= {5, -4, 6, -1 };  //creating an array
    int n = sizeof(arr)/sizeof(arr[0]); //size of the array
    int low = 0, high = n-1;
    cout<<"maximum subarray sum is"<<maxSubArraySum(arr,low,high);
    return 0;
}
Try It

 


Next > < Prev
Scroll to Top