Code:
#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 "<
cin>>a[i];
}
// Print the maximum sub-array sum.
cout<<"\nMaximum sub-array sum is: "<
return 0;
}
Output:
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 }
More C++ Programs:
