C++ Program to Find the Maximum Subarray Sum using Divide and Conquer

This is a C++ program to find the maximum subarray sum using divide and conquer approach.

Problem Description

1. This algorithm implements the divide and conquer approach to find the sub-array having a maximum sum.
2. The worst case time complexity of the algorithm is O(n*log(n)).

Problem Solution

1. Take the input of the integer array.
2. Using divide and conquer approach break the array.
3. Compute the individual sum and combine them, to get the global maximum sum.
4. Exit.

Program/Source Code

C++ Program to find the maximum subarray sum using divide and conquer approach.
This program is successfully run on Dev-C++ using TDM-GCC 4.9.2 MinGW compiler on a Windows system.

#include<iostream>
 
using namespace std;
 
// A function to find the maximum of two integers.
int max(int a, int b)
{
	return (a > b)? a:b;
}
 
// A function to find the maximum sum sub-array which includes mid of the sub-array.
int MaxCrossingSum(int arr[], int low, int mid, int high)
{
	// Include elements having index value less than or equal to the mid.
	int sum = 0;
	int leftpartsum = -1;
	for (int i = mid; i >= low; i--)
	{
		sum = sum + arr[i];
		if (sum > leftpartsum)
			leftpartsum = sum;
	}
 
	// Include elements having index value greater mid.
	sum = 0;
	int rightpartsum = -1;
	for (int i = mid+1; i <= high; i++)
	{
		sum = sum + arr[i];
		if (sum > rightpartsum)
			rightpartsum = sum;
    }
 
	// Return sum of elements on left and right of mid.
	return leftpartsum + rightpartsum;
}
 
// Returns sum of maxium subarray sum.
int MaxSubArraySum(int arr[], int low, int high)
{
	int mid;
	// If low index is equal to the high index h then the subarray contains only one element.
	if (low == high)
		return arr[low];
 
	// Otherwise find the mid index and proceed.
	mid = (low + high)/2;
 
	// Maximum sum sub-array can be either in the left part, right part or covering elements from both parts.
	return max(max(MaxSubArraySum(arr, low, mid), MaxSubArraySum(arr, mid+1, high)), MaxCrossingSum(arr, low, mid, high));
}
 
int main()
{
	int n, i;
	cout<<"Enter the number of data element in the array: ";
	cin>>n;
 
    int a[n];
	for(i = 0; i < n; i++)
	{
		cout<<"Enter element "<<i+1<<": ";
		cin>>a[i];
	}
 
	// Print the maximum sub-array sum.
	cout<<"\nMaximum sub-array sum is: "<<MaxSubArraySum(a, 0, n-1);
 
	return 0;
}
Program Explanation

1. Take the input of the number of elements in the array and the data array.
2. Call MaxSubArraySum(), with data array, start and end index in the argument list.
3. Inside MaxSubArraySum(), recursively break the array into two equal parts.
4. Compare the sub-array sum from the left part, right part and the combined sum of the array.
5. For combined sum, call MaxCrossingSum(), it computes the right and left part sum and return their addition.
6. Return to main and print the maximum sub-array sum.
7. Exit.

advertisement
advertisement
Runtime Test Cases
Case 1:
Enter the number of data element in the array: 10
Enter element 1: 1
Enter element 2: 2
Enter element 3: 5
Enter element 4: -9
Enter element 5: 6
Enter element 6: 9
Enter element 7: -10
Enter element 8: 2
Enter element 9: 3
Enter element 10: 1
 
Maximum sub-array sum is: 15
Case 2:
Enter the number of edges for the random graphs: 50
 
The generated random graph is:
        1-> { 15   3   17    }
        2-> { 8   8   12   17   12   4   7   10    }
        3-> { 5   16   14   13   14   18   11   1   19    }
        4-> { 12   2   10   7    }
        5-> { 10   3   12   14   8   9   15   20    }
        6-> { 6   7    }
        7-> { 8   9   6   2   17   4    }
        8-> { 2   2   17   7   20   5    }
        9-> { 14   7   5   14   12    }
        10-> { 5   13   19   11   4   2    }
        11-> { 3   10   11    }
        12-> { 2   5   19   4   2   9    }
        13-> { 3   10    }
        14-> { 3   3   5   9   9    }
        15-> { 1   16   5    }
        16-> { 3   19   15   17    }
        17-> { 8   2   16   1   7    }
        18-> { 3   20   19    }
        19-> { 19   16   12   10   18   3    }
        20-> { 8   18   5    }

Sanfoundry Global Education & Learning Series – C++ Algorithms.
To practice all C++ Algorithms, here is complete set of 1000 C++ Algorithms.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.