Question

2.4.3 Finding the Largest Value in a Sorted or Unsorted Array Suppose that you have an array anarray of integers in any order, and you want to find the largest value. You could construct an iterative solution without too much difficulty, but instead let's consider a recursive formulation: 1 array has only one untry YARDY is the enery in andera also it (anay has more than one entry Arayil the next Bahay (Ioft helt of an ezay) and Maxray right halt of andera Notice that this strategy fits the divide-and-conquer model that the previous binary search algorithm used. That is, we proceed by dividing the problem and conquering the subproblems, as Figure 2-12 illustrates. However, there is a difference between this algorithm and the binary search algorithm. Although the binary search algorithm conquers only one of its subproblems at each step, maxarray conquers both. Because both subproblems are solved recursively, this approach is called multipath recursion. After maxarray conquers the subproblems, it must reconcile the two solutions—that is, it must find the maximum of the two maximums. Figure 2-13 illustrates the computations that are necessary to find the largest integer in the array that contains 1, 6, 8, and 3 (denoted here by <1,6,8, 3>).

1. Implement the algorithm maxArray, discussed in Section 2.4.3, as a C++ function.

2. Make sure the following requirements are met.

3. Program must compile and run.
4. maxArray function must be a recursive template function.
5. Add a main function to test the maxArray function so that you have a complete program.
6. Test the maxArray function on two arrays of different types.
7. Name the program maxarray.cpp. Make sure the following requirements are met.

Answer 1

#include <iostream>
#include<climits>
using namespace std;
void maxArray(int arr[],int low,int high,int& max)
{
    // if array contains only one element
        if (low==high)
        {
                if (max < arr[low])
                        max = arr[low];
                return;
        }
        // if array contains only two elements
        if (high-low==1)
        {
                if(arr[low]<arr[high])
                {
                        if(max<arr[high])
                                max=arr[high];
                }
                else
                {
            if(max<arr[low])
                                max=arr[low];
                }
                return;
        }
        int mid=(low+high)/2;

        // recur for left sub-array
        maxArray(arr,low,mid,max);
        // recur for right sub-array
        maxArray(arr,mid+1,high,max);
}

int main()
{
        int arr1[]={1,6,8,3};
        int arr2[]={21,98,23,4,1,43,6};
        int n=sizeof(arr1)/sizeof(arr1[0]);

        int max=INT_MIN;
        maxArray(arr1,0,n-1,max);
        cout << "The maximum element in the array 1 is " << max;
        n=sizeof(arr2)/sizeof(arr2[0]);
        maxArray(arr2,0,n-1,max);
        cout << "\nThe maximum element in the array 2 is " << max;

        return 0;
}

We divided the array recursively into two equal parts and update the value of max.

I tried to explain the code with the help of comment and recognizable variables

Feel free to ask any query related to code or DIVIDE AND CONQUER Algorithm which we are using here.