Maximum Element in an Array which is Increasing and then Decreasing

Problem Statement

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.

Implementation

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

Java Program for Maximum element in an array

import java.util.Scanner;
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int max = -1; 
        for(int i = 0; i <= n-1; i++) 
        { 
            if(a[i]>max) 
            { 
                max = a[i]; 
            } 
        } 
        System.out.println("Maximum element:"+max); 
        }
}

5
1 3 5 2 1

5

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.

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.

Implementation

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

import java.util.Scanner;
class sum
{
    public static 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);
       }
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        System.out.println("Maximum element:"+FindMax(a,0,n-1)); 
    }
}

7
6 4 3 2 98 3 1

98