In rearrange given array in maximum minimum form problem, we have given a sorted array containing N elements. Rearrange the given sorted array of positive integers, such that alternative elements are ith max and ith min. See below for the better understanding for rearrangement of elements-

Array[0] = maximum value of the array, Array[1] = minimum value of the array, Array[2] = second maximum value of the array, Array[3] = second minimum value of the array, Array[4] = 3rd maximum value of the arrayÂ â€¦… and so on.

## Example

**Input**

7

arr[] = {1, 2, 3, 4, 5, 6, 7}

**Output**

arr[] = {7, 1, 6, 2, 5, 3, 4}

## Algorithm for Rearrange given Array in Maximum Minimum Form

**1.**Â Create an auxiliary dummy array to store the modified array.

**2.**Â Initialize low and high as the corner indices of the array.

**3.**Â For copying alternative max and min store a variable X and initialize True, if X = True we copy max value and if X = False we copy min value.

**4.** Run a loop to copy elements into the auxiliary array. After copying an element into the new array reverse the value of X.

**5.** If X is True copy element from the end and moves backward if X is False copy element from the front and moves forward.

**6.** Copy the auxiliary array into the given array.

**7.**Â Print the array, the elements will be rearranged.

## C++ Program for Rearrange given Array in Maximum Minimum Form

#include <bits/stdc++.h> using namespace std; //function to rearrange the given sorted array in maximum minimum form void RearrangeMaxMin(int array[], int N) { int temp[N];//auxilary dummy array with all zeroes for (int i=0; i<N; i++) { temp[i] = 0; } int low=0, high=N-1; // corner indices of the array int X = true; // indication for which element should be copied //copying elements into the temp array //according to the given condition for (int i=0; i<N; i++) { if(X) { temp[i] = array[high--]; } else { temp[i] = array[low++]; } X = !X; } for (int i=0; i<N; i++) { array[i] = temp[i]; } } //function to print the given array int PrintArray(int array[],int N) { for (int i=0; i<N; i++) { cout << array[i] << " "; } } // main function int main() { int array[] = {1, 2, 3, 4, 5, 6, 7, 8, 9}; int N = sizeof(array)/sizeof(array[0]); cout << "Input array\n"; PrintArray(array,N); RearrangeMaxMin(array,N); cout << "\nOutput array\n"; PrintArray(array,N); return 0; }

Input array 1 2 3 4 5 6 7 8 9 Output array 9 1 8 2 7 3 6 4 5

## Complexity Analysis for Rearrange given Array in Maximum Minimum Form

### Time Complexity

**O(N)** where n is the number of elements present in the given array. Here we use two pointer methods and which run at most n times. So, we can say the time complexity is linear in this case.

### Space Complexity

**O(N)** because we use an auxiliary array for storing the elements in the maximum and minimum form.