Home » Interview Questions » Array Interview Questions » Maximum Subarray Sum using Divide and Conquer

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.


arr[] = {3, -4, 6, 2, -1 }
subarray is {6, 2}

Time Complexity: O(nlogn)


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;
		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;

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions