Given an array, it can be of 4 types
(a) Ascending
(b) Descending
(c) Ascending Rotated
(d) Descending Rotated
Find out which kind of array it is and return the maximum of that array.
(a) Ascending
(b) Descending
(c) Ascending Rotated
(d) Descending Rotated
Find out which kind of array it is and return the maximum of that array.
// descending, clockwise rotated or anti-clockwise
// rotated.
#include<bits/stdc++.h>
using namespace std;
// Function to find the type of an array
// and maximum element in it.
void findType( int arr[] , int n)
{
// boolean variables to check if array is increasing or decreasing
bool isIncreasing = false , isDecreasing = false;
for( int i = 1 ; i < n ; ++i){
// increasing value found
if(arr[i-1] < arr[i]){
isIncreasing = true;
// if the array was decreasing earlier then its Descending Ascending and maximum is current element
// example : 2 1 5 4 3
if(isDecreasing){
cout << "Descending rotated Max : " << arr[i] << "\n";
return;
}
}
// decreasing value found
else if (arr[i-1] > arr[i]){
isDecreasing = true;
// if the array was increasing earlier then its Ascending Descending and maximum is i-1 element
// eg 4 5 1 2 3
if(isIncreasing){
cout << "Ascending rotated Max : " << arr[i-1] << "\n";
return;
}
}
}
// else array is purely ascending or descending
if(isIncreasing)
cout << "Ascending Max : " << arr[n-1] << "\n";
else
cout <<"Descedning Max : " << arr[0] << "\n";
}
// Driver code
int main()
{
int arr1[] = { 4, 5, 6, 1, 2, 3}; // Ascending rotated
int n = sizeof (arr1) / sizeof (arr1[0]);
findType(arr1, n);
int arr2[] = { 2, 1, 7, 5, 4, 3}; // Descending rotated
n = sizeof(arr2) / sizeof (arr2[0]);
findType(arr2, n);
int arr3[] = { 1, 2, 3, 4, 5, 8}; // Ascending
n = sizeof(arr3) / sizeof (arr3[0]);
findType(arr3, n);
int arr4[] = { 9, 5, 4, 3, 2, 1}; // Descending
n = sizeof(arr4) / sizeof (arr4[0]);
findType(arr4, n);
return 0;
}