Illustrate the operation of FIND-MAXIMUM-SUBARRAY on the array A = {13, -3, -25,
ID: 3873590 • Letter: I
Question
Illustrate the operation of FIND-MAXIMUM-SUBARRAY on the array
A = {13, -3, -25, 20, -3, -16, -23, 18}
FIND-MAXIMUM-SUBARRAY.A; low; high/ 1 if high-low 2return (low, high, A[lowl) // base case: only one element 3 else mid = (low + hig/2 4 (left-low; left-high; left-sum-FIND-MAXIMUM-SUBARRAY(A; low; mid) 5 (right-low; right-high; right-sum) -FIND-MAXIMUM-SUBARRAY(A; mid + high) 6 . (cross-low. cross-high; cross-sum) =FIND-MAX- ; low; mid; high) 7if left-sum > right-sum and left-sum > cross-sum CROSSING-SUBARRAY(A return (left-low; left-high; left-sum) 9 elseif right-sum > left-sum and right-sum >cross-sum return (right-low; right-high; right-sum) 11else return (cross-low; cross-high; cross-sum) 1. (10) Illustrate the operation of FIND-MAXIMUM-SUBARRAY on the array A { 13,-3,-25, 20,-3,-16,-23, 18}Explanation / Answer
// Maximum subarray sum program.
#include <stdio.h>
#include <limits.h>
// This max function is used to find maximum of two numbers.
int max(int m, int n) { return (m > n)? m : n; }
// This max function is used to find maximum of three numbers.
int max(int p, int q, int r) { return max(max(p, q), r); }
// This function find the maximum possible sum in arr[], such that arr[m] is part of it.
int maximumCrossingSum(int arr[], int low, int mid, int high)
{
// include the elements on left of mid.
int sum = 0;
int left_sum = INT_MIN;
for (int i = mid; i >= low; i--)
{
sum = sum + arr[i];
if (sum > left_sum)
left_sum = sum;
}
// include the elements on right of the mid
sum = 0;
int right_sum = INT_MIN;
for (int i = mid+1; i <= high; i++)
{
sum = sum + arr[i];
if (sum > right_sum)
right_sum = sum;
}
// Return sum of the elements on left and right of the mid
return left_sum + right_sum;
}
// Returns the sum of maxium-sum-of-subarray in array[l..h]
int maximumSubArraySum(int arr[], int low, int high)
{
// Initial Case: Only one element
if (low == high) // if low equal to high.
return arr[low];
// Finding the middle point
int mid = (low + high)/2;
/* Return maximum of following three possible cases
a) Maximum-subarray-of-sum in left half
b) Maximum-subarray-of-sum in right half
c) Maximum-subarray-of-sum such that the subarray crosses the midpoint */
return max(maximumSubArraySum(arr, low, mid),
maximumSubArraySum(arr, mid+1, high),
maximumCrossingSum(arr, low, mid, high));
}
/*Driver program to test maxSubArraySum*/
int main()
{
int arr[] = {13, -3, -25, 20, -3, -16, -23, 18};
int n = sizeof(arr)/sizeof(arr[0]);
int max_sum = maximumSubArraySum(arr, 0, n-1);
printf("Maximum contiguous sum is %d", max_sum);
getchar();
return 0;
}
/*
output:-
Maximum contiguous sum is 20
*/