Home » Technical Interview Questions » Array Interview Questions » Maximum Element in an Array which is Increasing and then Decreasing

Maximum Element in an Array which is Increasing and then Decreasing


Reading Time - 2 mins


Difficulty Level Easy

In the given array which contains n elements. Elements are stored in such a way that first k elements are in increasing order and then n-k elements in 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

Approach 1

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.

C++ Program for Maximum element in an array

#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;
}
Maximum element:55

Complexity Analysis for Maximum element in an array

Time Complexity

O(n) where n is the number of elements present in the array. Here we iterate all the elements and check the condition where the next element is greater than the previous element. Once this condition hits then we print our answer and break the loop.

READ  Maximum length subsequence with difference between adjacent elements as either 0 or 1

Space Complexity

O(1) because we don’t use much auxiliary space here.

Approach 2

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 the left part of the mid. So, search in the left part.
  3. If mid is less than it’s next and greater than previous element, then maximum will be in the right part of mid. So, search in the right part.

C++ Program for Maximum element in an array

#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;
}
Maximum element:55
Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions