Sum Of Max And Min

Steps:

1. Create two variables maximum and minimum, and initialise with arr[0].
2. Run a loop from i = 1 to N-1 and do:
   1. If arr[i] > maximum, then make maximum = arr[i].
   2. Else If arr[i] < minimum, then make minimum = arr[i].
3. Note that, the above step, takes 2 * (N - 1) comparisons in the worst case when the array is sorted in decreasing order.
4. At last return maximum + minimum.

The idea is to use a divide and conquer approach in order to reduce the number of comparisons. We divide the array into two equal parts and find the maximum and minimum element of each part recursively. Then we compare the maximum and minimum of both parts in order to find the maximum and minimum element of the whole array.

Steps:

1. Create a data type that contains two integers as maximum and minimum. The first integer denotes the maximum value whereas the second one denotes the minimum value. Let’s denote the name of this variable as maxMin.
2. Implement a recursive function say findMaxMin(arr, 0, N-1).
3. Finally, return the sum of maximum and minimum.

pair<int, int> findMaxMin(arr, left, right):

1. If left == right, i.e. only one element is present in the array, then return {arr[left], arr[right]}.
2. If right == left + 1, i.e. only two elements are present in the array, then:
   1. If arr[left] > arr[right], then return {arr[left], arr[right]}.
   2. Else, return {arr[right], arr[left]}.
3. Create a mid variable and make mid = (left + right) / 2.
4. Create two more pairs of integers, say leftAns and rightAns in order to store the result of the left half and right half respectively.
5. Call the recursive function from left to mid for the leftAns and mid + 1 to right for the rightAns, i.e. leftAns = findMaxMin(arr, left, mid) and rightAns = findMaxMin(arr, mid+1, right).
6. Finally, return the maximum among the maximum of leftAns and rightAns and minimum among the minimum of leftAns and rightAns i.e. {max(leftAns.first, rightAns.first), min(leftAns.second, rightAns.second)}.