Maximum element in an array which is increasing and then decreasing

In the given array elements are first increasing and then decreasing from there, we need to find the maximum element in the array.

Example

a)    Input array : [15, 25, 35, 45, 55, 50, 40, 30, 20, 10]

The given array is increasing from 15 to 55 and then decreasing to 10,

Output : 55

b)    Input array : [1, 3, 9, 8, 6, 4, 2]

The given array is increasing from 1 to 9 and then decreasing to 2,

Output : 9

Method 1

Time complexity : O(n)

Algorithm

  1. Initialize maximum = INT_MIN.
  2. Traverse in the array and compare all the elements with maximum, if maximum < array[i] update maximum.
  3. After traversing the array completely, print maximum.

Algorithm working

C++ Program

#include <bits/stdc++.h>
#include <limits.h>

using namespace std;
 
 
/*Main function*/
int main()
{
   int input_array[] = {15,25,35,45,55,50,40,30,20,10};
   int N = sizeof(input_array)/sizeof(input_array[0]);
   int max = INT_MIN;
   for(int i = 0; i <= N-1; i++)
   {
       if (input_array[i] > max)
       {
          max = input_array[i];
       }
   }
  cout<<"Maximum element:"<<max; 
  return 0;
}
Try It
 

Method 2

Time complexity : O(logN)

Algorithm

Here, we use a modified Binary search.

  1. We compare mid element with previous and next elements, if mid is greater than previous and next, mid is maximum so, return maximum.
  2. If mid is greater than its next element and smaller than its previous element, then maximum will be in left part of the mid. So, search in left part.
  3. If mid is less than its next and greater than previous element, then maximum will be in right part of mid. So, search in right part.

Algorithm working

a)

b)

C++ Program

#include <bits/stdc++.h>
#include <limits.h>

using namespace std;

int FindMax(int array[], int low, int high)
{
   if(low == high)//only one element
   {
     return array[low];
   }
   if((high- 1 == low))//if two elements present, return maximum element
   {
      if(array[low] >= array[high])
      {
        return array[low];
      }
      else
      {
        return array[high];
      }
   }     
   int mid = (low + high)/2;
   //If mid is greater than previous and next, mid is maximum so, return maximum
   if(array[mid]>array[mid+1] && array[mid]>array[mid-1])
   {
      return array[mid];
   }
   //If mid is greater than its next element and smaller than its previous element
   //then maximum will be in left part of the mid
   if(array[mid]>array[mid+1] && array[mid]<array[mid-1])
   {
     return FindMax(array,low,mid-1);
   }
   //If mid is less than its next and greater than previous element
   //then maximum will be in right part of mid
   else
   {
     return FindMax(array,mid+1,high);
   }
}
 
/*Main function to print maximimum*/
int main()
{
   int input_array[] = {15,25,35,45,55,50,40,30,20,10};
   int N = sizeof(input_array)/sizeof(input_array[0]);
   cout<<"Maximum element:"<<FindMax(input_array,0,N-1);
   return 0;
}
Try It


Next > < Prev
Scroll to Top