This is a C++ program to find the maximum subarray sum using divide and conquer approach.
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)).
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.
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; }
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.
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.