Find the maximum element in an array which is first increasing and then decreasing

Last Updated : 14 Aug, 2023

Given an array of integers which is initially increasing and then decreasing, find the maximum value in the array.
Examples :

Input: arr[] = {8, 10, 20, 80, 100, 200, 400, 500, 3, 2, 1}
Output: 500
Input: arr[] = {1, 3, 50, 10, 9, 7, 6}
Output: 50
Corner case (No decreasing part)
Input: arr[] = {10, 20, 30, 40, 50}
Output: 50
Corner case (No increasing part)
Input: arr[] = {120, 100, 80, 20, 0}
Output: 120

Method 1 (Linear Search): We can traverse the array and keep track of maximum and element. And finally return the maximum element.

Implementation:

C++

// C++ program to find maximum 
// element 
#include <bits/stdc++.h>
using namespace std;
 
// function to find the maximum element 
int findMaximum(int arr[], int low, int high) 
{ 
    int max = arr[low]; 
    int i; 
    for (i = low + 1; i <= high; i++) 
    { 
        if (arr[i] > max) 
            max = arr[i]; 
         
        // break when once an element is smaller than 
        // the max then it will go on decreasing 
        // and no need to check after that 
        else
            break; 
    } 
    return max; 
} 
 
/* Driver code*/
int main() 
{ 
    int arr[] = {1, 30, 40, 50, 60, 70, 23, 20}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    cout << "The maximum element is " << findMaximum(arr, 0, n-1); 
    return 0; 
} 
 
// This is code is contributed by rathbhupendra

C

// C program to find maximum
// element
#include <stdio.h>
 
// function to find the maximum element
int findMaximum(int arr[], int low, int high)
{
int max = arr[low];
int i;
for (i = low+1; i <= high; i++)
{
    if (arr[i] > max)
        max = arr[i];
// break when once an element is smaller than 
// the max then it will go on decreasing 
// and no need to check after that
    else
        break;
}
return max;
}
 
/* Driver program to check above functions */
int main()
{
int arr[] = {1, 30, 40, 50, 60, 70, 23, 20};
int n = sizeof(arr)/sizeof(arr[0]);
printf("The maximum element is %d", findMaximum(arr, 0, n-1));
getchar();
return 0;
}

Java

// java program to find maximum
// element
 
class Main
{   
    // function to find the 
    // maximum element
    static int findMaximum(int arr[], int low, int high)
    {
       int max = arr[low];
       int i;
       for (i = low; i <= high; i++)
       {
           if (arr[i] > max)
              max = arr[i];
       }
       return max;
    }
     
    // main function
    public static void main (String[] args) 
    {
        int arr[] = {1, 30, 40, 50, 60, 70, 23, 20};
        int n = arr.length;
        System.out.println("The maximum element is "+ 
                            findMaximum(arr, 0, n-1));
    }
}

Python3

# Python3 program to find 
# maximum element
 
def findMaximum(arr, low, high):
    max = arr[low]
    i = low
    for i in range(high+1):
        if arr[i] > max:
            max = arr[i]
    return max
 
# Driver program to check above functions */
arr = [1, 30, 40, 50, 60, 70, 23, 20]
n = len(arr)
print ("The maximum element is %d"%
        findMaximum(arr, 0, n-1))
 
# This code is contributed by Shreyanshi Arun.

C#

// C# program to find maximum
// element
using System;
 
class GFG
{
    // function to find the 
    // maximum element
    static int findMaximum(int []arr, int low, int high)
    {
        int max = arr[low];
        int i;
        for (i = low; i <= high; i++)
        {
            if (arr[i] > max)
                max = arr[i];
        }
        return max;
    }
     
    // Driver code
    public static void Main () 
    {
        int []arr = {1, 30, 40, 50, 60, 70, 23, 20};
        int n = arr.Length;
        Console.Write("The maximum element is "+ 
                        findMaximum(arr, 0, n-1));
    }
}
 
// This code is contributed by Sam007

Javascript

<script>
 
// Javascript program to find maximum
// element
 
// function to find the maximum element
function findMaximum(arr, low, high)
{
    var max = arr[low];
    var i;
    for (i = low + 1; i <= high; i++)
    {
        if (arr[i] > max)
            max = arr[i];
         
        // break when once an element is smaller than
        // the max then it will go on decreasing
        // and no need to check after that
        else
            break;
    }
    return max;
}
 
/* Driver code*/
var arr = [1, 30, 40, 50, 60, 70, 23, 20];
var n = arr.length;
document.write("The maximum element is " + findMaximum(arr, 0, n-1));
 
</script>

PHP

<?php
// PHP program to Find the maximum 
// element in an array which is first
// increasing and then decreasing
 
function findMaximum($arr, $low, $high)
{
$max = $arr[$low];
$i;
for ($i = $low; $i <= $high; $i++)
{
    if ($arr[$i] > $max)
        $max = $arr[$i];
}
return $max;
}
 
// Driver Code
$arr = array(1, 30, 40, 50, 
             60, 70, 23, 20);
$n = count($arr);
echo "The maximum element is ", 
      findMaximum($arr, 0, $n-1);
 
// This code is contributed by anuj_67.
?>

Output

The maximum element is 70

Time Complexity : O(n)

Auxiliary Space: O(1)

Method 2 (Binary Search – Recursive Solution)

The iterative approach of Binary search to find the maximum element in an array which is first increasing and then decreasing.
The standard binary search approach can be modified in the following ways :-

If the mid element is greater than both of its adjacent elements, then mid is the maximum.
If the mid element is smaller than its next element then we should try to search on the right half of the array. So, make, low = mid + 1. Example array : {2, 4, 6, 8, 10, 3, 1}
If the mid element is greater than the next element, similarly we should try to search on the left half. So, make, high = mid – 1. Example array: {3, 50, 10, 9, 7, 6}

Implementation:

C++

#include <bits/stdc++.h>
using namespace std;
 
// Recursive solution for finding bitonic point
int findMaximum(int arr[], int low, int high)
{
      // if there is only one element
    if (low == high)
        return arr[high];
     
      // finding the mid index
    int mid = low + (high - low) / 2;
     
      // if the value of mid index is greater than left and right value
    if (arr[mid] > arr[mid - 1] and arr[mid] > arr[mid + 1])
        return arr[mid];
     
      // if value on mid index is greater than next index
      // shift the search space to right half
    else if (arr[mid] < arr[mid + 1])
        return findMaximum(arr, mid + 1, high);
     
      // else vice-versa i.e. to left half
    else
        return findMaximum(arr, low, mid - 1);
}
 
/* Driver code */
int main()
{
    int arr[] = { 1, 3, 50, 10, 9, 7, 6 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "The maximum element is "
         << findMaximum(arr, 0, n - 1);
    return 0;
}
 
// This is code is contributed by rajdeep999

C

#include <stdio.h>
 
int findMaximum(int arr[], int low, int high)
{
 
   /* Base Case: Only one element is present in arr[low..high]*/
   if (low == high)
     return arr[low];
 
   /* If there are two elements and first is greater than
      the first element is maximum */
   if ((high == low + 1) && arr[low] >= arr[high])
      return arr[low];
 
   /* If there are two elements and second is greater than
      the second element is maximum */
   if ((high == low + 1) && arr[low] < arr[high])
      return arr[high];
 
   int mid = (low + high)/2;   /*low + (high - low)/2;*/
 
   /* If we reach a point where arr[mid] is greater than both of
     its adjacent elements arr[mid-1] and arr[mid+1], then arr[mid]
     is the maximum element*/
   if ( arr[mid] > arr[mid + 1] && arr[mid] > arr[mid - 1])
      return arr[mid];
 
   /* If arr[mid] is greater than the next element and smaller than the previous 
    element then maximum lies on left side of mid */
   if (arr[mid] > arr[mid + 1] && arr[mid] < arr[mid - 1])
     return findMaximum(arr, low, mid-1);
   else // when arr[mid] is greater than arr[mid-1] and smaller than arr[mid+1]
     return findMaximum(arr, mid + 1, high);
}
 
/* Driver program to check above functions */
int main()
{
   int arr[] = {1, 3, 50, 10, 9, 7, 6};
   int n = sizeof(arr)/sizeof(arr[0]);
   printf("The maximum element is %d", findMaximum(arr, 0, n-1));
   getchar();
   return 0;
}

Java

// java program to find maximum
// element
 
class Main
{   
    // function to find the 
    // maximum element
    static int findMaximum(int arr[], int low, int high)
    {
      
       /* Base Case: Only one element is 
          present in arr[low..high]*/
       if (low == high)
         return arr[low];
      
       /* If there are two elements and 
          first is greater than the first 
          element is maximum */
       if ((high == low + 1) && arr[low] >= arr[high])
          return arr[low];
      
       /* If there are two elements and 
          second is greater than the second 
          element is maximum */
       if ((high == low + 1) && arr[low] < arr[high])
          return arr[high];
         
       /*low + (high - low)/2;*/
       int mid = (low + high)/2;   
      
       /* If we reach a point where arr[mid] 
          is greater than both of its adjacent 
          elements arr[mid-1] and arr[mid+1], 
          then arr[mid] is the maximum element*/
       if ( arr[mid] > arr[mid + 1] && arr[mid] > arr[mid - 1])
          return arr[mid];
      
       /* If arr[mid] is greater than the next 
          element and smaller than the previous 
          element then maximum lies on left side 
          of mid */
       if (arr[mid] > arr[mid + 1] && arr[mid] < arr[mid - 1])
         return findMaximum(arr, low, mid-1);
       else
         return findMaximum(arr, mid + 1, high);
    }
     
    // main function
    public static void main (String[] args) 
    {
        int arr[] = {1, 3, 50, 10, 9, 7, 6};
        int n = arr.length;
        System.out.println("The maximum element is "+ 
                            findMaximum(arr, 0, n-1));
    }
}

Python3

def findMaximum(arr, low, high):
    # Base Case: Only one element is present in arr[low..high]*/
    if low == high:
        return arr[low]
  
    # If there are two elements and first is greater than
    # the first element is maximum */
    if high == low + 1 and arr[low] >= arr[high]:
        return arr[low];
  
    # If there are two elements and second is greater than
    # the second element is maximum */
    if high == low + 1 and arr[low] < arr[high]:
        return arr[high]
  
    mid = (low + high)//2   #low + (high - low)/2;*/
  
    # If we reach a point where arr[mid] is greater than both of
    # its adjacent elements arr[mid-1] and arr[mid+1], then arr[mid]
    # is the maximum element*/
    if arr[mid] > arr[mid + 1] and arr[mid] > arr[mid - 1]:
        return arr[mid]
  
    # If arr[mid] is greater than the next element and smaller than the previous 
    # element then maximum lies on left side of mid */
    if arr[mid] > arr[mid + 1] and arr[mid] < arr[mid - 1]:
        return findMaximum(arr, low, mid-1)
    else: # when arr[mid] is greater than arr[mid-1] and smaller than arr[mid+1]
        return findMaximum(arr, mid + 1, high)
  
# Driver program to check above functions */
arr = [1, 3, 50, 10, 9, 7, 6]
n = len(arr)
print ("The maximum element is %d"% findMaximum(arr, 0, n-1))
 
# This code is contributed by Shreyanshi Arun.

C#

// C# program to find maximum
// element
using System;
 
class GFG
{
    // function to find the 
    // maximum element
    static int findMaximum(int []arr, int low, int high)
    {
     
    /* Base Case: Only one element is 
        present in arr[low..high]*/
    if (low == high)
        return arr[low];
     
    /* If there are two elements and 
        first is greater than the first 
        element is maximum */
    if ((high == low + 1) && arr[low] >= arr[high])
        return arr[low];
     
    /* If there are two elements and 
        second is greater than the second 
        element is maximum */
    if ((high == low + 1) && arr[low] < arr[high])
        return arr[high];
         
    /*low + (high - low)/2;*/
    int mid = (low + high)/2; 
     
    /* If we reach a point where arr[mid] 
        is greater than both of its adjacent 
        elements arr[mid-1] and arr[mid+1], 
        then arr[mid] is the maximum element*/
    if ( arr[mid] > arr[mid + 1] && arr[mid] > arr[mid - 1])
        return arr[mid];
     
    /* If arr[mid] is greater than the next 
        element and smaller than the previous 
        element then maximum lies on left side 
        of mid */
    if (arr[mid] > arr[mid + 1] && arr[mid] < arr[mid - 1])
        return findMaximum(arr, low, mid-1);
    else
        return findMaximum(arr, mid + 1, high);
    }
     
    // main function
    public static void Main() 
    {
        int []arr = {1, 3, 50, 10, 9, 7, 6};
        int n = arr.Length;
        Console.Write("The maximum element is "+ 
                            findMaximum(arr, 0, n-1));
    }
}
// This code is contributed by Sam007

Javascript

<script>
   
function findMaximum( arr, low, high) 
{  
   
    /* Base Case: Only one element is present in arr[low..high]*/
    if (low == high) 
        return arr[low]; 
       
    /* If there are two elements and first is greater than 
        the first element is maximum */
    if ((high == low + 1) && arr[low] >= arr[high]) 
        return arr[low]; 
       
    /* If there are two elements and second is greater than 
        the second element is maximum */
    if ((high == low + 1) && arr[low] < arr[high]) 
        return arr[high]; 
       
     mid = (low + high)/2; 
     /*low + (high - low)/2;*/
       
    /* If we reach a point where arr[mid] is greater than both of 
        its adjacent elements arr[mid-1] and arr[mid+1], then arr[mid] 
        is the maximum element*/
    if ( arr[mid] > arr[mid + 1] && arr[mid] > arr[mid - 1]) 
        return arr[mid]; 
       
    /* If arr[mid] is greater than the next
        element and smaller than the previous 
        element then maximum lies on left side of mid */
    if (arr[mid] > arr[mid + 1] && arr[mid] < arr[mid - 1]) 
        return findMaximum(arr, low, mid-1); 
           
        // when arr[mid] is greater than arr[mid-1]
        // and smaller than arr[mid+1]
        return findMaximum(arr, mid + 1, high); 
} 
   
/* Driver code */
  
     arr = new Array(1, 3, 50, 10, 9, 7, 6); 
     n = arr.length; 
document.write("The maximum element is" + "\n" + findMaximum(arr, 0, n-1)); 
 
// This code is contributed by simranarora5sos
 </script>

PHP

<?php
// PHP program to Find the maximum 
// element in an array which is 
// first increasing and then decreasing
 
function findMaximum($arr, $low, $high)
{
 
    /* Base Case: Only one element 
       is present in arr[low..high]*/
    if ($low == $high)
        return $arr[$low];
     
    /* If there are two elements 
       and first is greater than
       the first element is maximum */
    if (($high == $low + 1) && 
        $arr[$low] >= $arr[$high])
        return $arr[$low];
     
    /* If there are two elements
       and second is greater than
       the second element is maximum */
    if (($high == $low + 1) && 
         $arr[$low] < $arr[$high])
        return $arr[$high];
     
    /*low + (high - low)/2;*/
    $mid = ($low + $high) / 2; 
     
    /* If we reach a point where
       arr[mid] is greater than
       both of its adjacent elements
       arr[mid-1] and arr[mid+1],
       then arr[mid] is the maximum
       element */
    if ( $arr[$mid] > $arr[$mid + 1] &&
         $arr[$mid] > $arr[$mid - 1])
        return $arr[$mid];
     
    /* If arr[mid] is greater than 
       the next element and smaller 
       than the previous element then
       maximum lies on left side of mid */
    if ($arr[$mid] > $arr[$mid + 1] && 
        $arr[$mid] < $arr[$mid - 1])
        return findMaximum($arr, $low, $mid - 1);
     
    // when arr[mid] is greater than 
    // arr[mid-1] and smaller than
    // arr[mid+1]    
    else
        return findMaximum($arr, 
                           $mid + 1, $high);
}
 
// Driver Code
$arr = array(1, 3, 50, 10, 9, 7, 6);
$n = sizeof($arr);
echo("The maximum element is "); 
echo(findMaximum($arr, 0, $n-1));
 
// This code is contributed by nitin mittal.
?>

Output

The maximum element is 50

Time Complexity : O(logn)

Auxiliary Space : O(logn)
This method works only for distinct numbers. For example, it will not work for an array like {0, 1, 1, 2, 2, 2, 2, 2, 3, 4, 4, 5, 3, 3, 2, 2, 1, 1}.

Method 3 (Binary Search – Iterative Solution)

If the mid element is greater than both of its adjacent elements, then mid is the maximum.
If the mid element is smaller than its next element then we should try to search on the right half of the array. So, make, low = mid + 1 .Example array : {2, 4, 6, 8, 10, 3, 1}
If the mid element is greater than the next element, similarly we should try to search on the left half. So, make, high = mid – 1. Example array : {3, 50, 10, 9, 7, 6}

Implementation:

C++

#include <iostream>
using namespace std;
 
int maxInBitonic(int arr[], int low, int high)
{
    // find out the size of the array
    // for edge case checking
    int n = high + 1;
 
    // main code goes as follows
    while (low <= high) {
        // find out the mid
        int mid = low + (high - low) / 2;
         
          // if mid index value is maximum 
        if(arr[mid] > arr[mid+1] and arr[mid] > arr[mid-1])
              return arr[mid];
 
        // reducing search space by moving to right
        else if (arr[mid] < arr[mid + 1])
            low = mid + 1;
 
        // reducing search space by moving to left
        else
            high = mid - 1;
    }
 
    return arr[high];
}
 
// Driver function
int main()
{
    int arr[] = { 1, 3, 50, 10, 9, 7, 6 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "The maximum element is "
         << maxInBitonic(arr, 0, n - 1);
    return 0;
}
 
// This code is contributed by rajdeep999

Java

import java.util.*;
 
class GFG{
 
static int maxInBitonic(int arr[], int l, int r)
{
 
    while (l <= r) {
 
        int m = l + (r - l) / 2; // m = (l + r) / 2
 
        /****Base Cases Starts*****/
       
         if(l==r)
        return arr[l];
       
        /* If there are two elements and first is greater
           then the first element is maximum */
        if ((r == l + 1) && arr[l] >= arr[r])
            return arr[l];
 
        /* If there are two elements and second is greater
           then the second element is maximum */
 
        if ((r == l + 1) && arr[l] < arr[r])
            return arr[r];
 
        /* If we reach a point where arr[mid] is greater
           than both of its adjacent elements arr[mid-1] and
           arr[mid+1], then arr[mid] is the maximum
           element*/
        if (arr[m] > arr[m + 1] && arr[m] > arr[m - 1])
            return arr[m];
 
        /****Base Case ends *****/
 
        // move to left with l and r=m-1
        if (arr[m] > arr[m + 1] && arr[m] < arr[m - 1])
            r = m - 1;
 
        else
            l = m + 1; // move to right with l=m+1 and r
    }
    // if we reach here, then element was
    // not present
    return -1;
}
 
// Driver function
public static void main(String[] args)
{
    int arr[] = { 1, 3, 50, 10, 9, 7, 6 };
    int n = arr.length;
    System.out.print("The maximum element is "
         + maxInBitonic(arr, 0, n - 1));
}
}
 
// This code is contributed by todaysgaurav 

Python3

# Python 3 program for the above approach
 
def maxInBitonic(arr, l, r) :
 
    while (l <= r) :
 
        m = int(l + (r - l) / 2) # m = (l + r) / 2
 
        #Base Cases Starts*****/
         
        if(l==r)
        return arr[l];
       
        # If there are two elements and first is greater
        # then the first element is maximum */
        if ((r == l + 1) and arr[l] >= arr[r]):
            return arr[l]
 
        # If there are two elements and second is greater
        # then the second element is maximum */
 
        if ((r == l + 1) and arr[l] < arr[r]):
            return arr[r]
 
        # If we reach a point where arr[mid] is greater
        # than both of its adjacent elements arr[mid-1] and
        # arr[mid+1], then arr[mid] is the maximum
        # element*/
        if (arr[m] > arr[m + 1] and arr[m] > arr[m - 1]):
            return arr[m]
 
        #***Base Case ends *****/
 
        # move to left with l and r=m-1
        if (arr[m] > arr[m + 1] and arr[m] < arr[m - 1]) :
            r = m - 1
 
        else :
            l = m + 1 # move to right with l=m+1 and r
     
    # if we reach here, then element was
    # not present
    return -1
 
# Driver function
arr = [ 1, 3, 50, 10, 9, 7, 6 ]
n = len(arr)
print("The maximum element is ", maxInBitonic(arr, 0, n - 1))
 
# This code is contributed by splevel62.

C#

using System;
 
class GFG{
 
static int maxInBitonic(int []arr, int l, int r)
{
 
    while (l <= r) {
 
        int m = l + (r - l) / 2; // m = (l + r) / 2
 
        /****Base Cases Starts*****/
       
          if(l==r)
        return arr[l];
       
        /* If there are two elements and first is greater
           then the first element is maximum */
        if ((r == l + 1) && arr[l] >= arr[r])
            return arr[l];
 
        /* If there are two elements and second is greater
           then the second element is maximum */
 
        if ((r == l + 1) && arr[l] < arr[r])
            return arr[r];
 
        /* If we reach a point where arr[mid] is greater
           than both of its adjacent elements arr[mid-1] and
           arr[mid+1], then arr[mid] is the maximum
           element*/
        if (arr[m] > arr[m + 1] && arr[m] > arr[m - 1])
            return arr[m];
 
        /****Base Case ends *****/
 
        // move to left with l and r=m-1
        if (arr[m] > arr[m + 1] && arr[m] < arr[m - 1])
            r = m - 1;
 
        else
            l = m + 1; // move to right with l=m+1 and r
    }
    // if we reach here, then element was
    // not present
    return -1;
}
 
// Driver function
public static void Main(String[] args)
{
    int []arr = { 1, 3, 50, 10, 9, 7, 6 };
    int n = arr.Length;
    Console.Write("The maximum element is "
         + maxInBitonic(arr, 0, n - 1));
}
}
 
// This code is contributed by shivanisinghss2110

Javascript

<script>
// JavaScript program
 
function maxInBitonic(arr, l, r)
{
 
    while (l <= r) {
 
        var m = l + (r - l) / 2; // m = (l + r) / 2
 
        /****Base Cases Starts*****/
         
        if(l==r)
        return arr[l];
         
        /* If there are two elements and first is greater
           then the first element is maximum */
        if ((r == l + 1) && arr[l] >= arr[r])
            return arr[l];
 
        /* If there are two elements and second is greater
           then the second element is maximum */
 
        if ((r == l + 1) && arr[l] < arr[r])
            return arr[r];
 
        /* If we reach a point where arr[mid] is greater
           than both of its adjacent elements arr[mid-1] and
           arr[mid+1], then arr[mid] is the maximum
           element*/
        if (arr[m] > arr[m + 1] && arr[m] > arr[m - 1])
            return arr[m];
 
        /****Base Case ends *****/
 
        // move to left with l and r=m-1
        if (arr[m] > arr[m + 1] && arr[m] < arr[m - 1])
            r = m - 1;
 
        else
            l = m + 1; // move to right with l=m+1 and r
    }
    // if we reach here, then element was
    // not present
    return -1;
}
 
// Driver function
    var arr = [ 1, 3, 50, 10, 9, 7, 6 ];
    var n = arr.length;
   document.write("The maximum element is "
         + maxInBitonic(arr, 0, n - 1));
 
 
// This code is contributed by shivanisinghss2110 
 
</script>

Output

The maximum element is 50

Time Complexity: O(log n)

Auxiliary Space: O(1)

Method 4 (Using Stack) :

1.Create an empty stack to hold the indices of the array elements.
2.Traverse the array from left to right until we find the maximum element. Push the index of each element onto the 
 stack as long as the element is less than or equal to the previous element.
3.Once we find an element that is greater than the previous element, we know that the maximum element has been
 reached. We can then pop all the indices from the 4.stack until we find an index whose corresponding element 
 is greater than the current element.
4.The maximum element is the element corresponding to the last index remaining on the stack.

Implementation of above approach :

C++

#include <bits/stdc++.h>
using namespace std;
 
int findMax(int arr[], int n)
{
    stack<int> s;
    int max = 0;
 
    // traverse the array from left to right
    for (int i = 0; i < n; i++) {
        // push the index onto the stack if the element is
        // less than or equal to the previous element
        if (s.empty() || arr[i] <= arr[s.top()]) {
            s.push(i);
        }
        else {
            // pop all the indices from the stack until we
            // find an index whose corresponding element is
            // greater than the current element
            while (!s.empty() && arr[i] > arr[s.top()]) {
                int index = s.top();
                s.pop();
                // update the maximum element
                if (arr[index] > max) {
                    max = arr[index];
                }
            }
            // push the current index onto the stack
            s.push(i);
        }
    }
 
    // the maximum element is the element corresponding to
    // the last index remaining on the stack
    while (!s.empty()) {
        int index = s.top();
        s.pop();
        if (arr[index] > max) {
            max = arr[index];
        }
    }
 
    return max;
}
int main()
{
 
    int arr[] = { 1, 3, 50, 10, 9, 7, 6 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "The maximum element is "
         << findMax(arr, n);
 
    return 0;
}

Java

import java.util.Stack;
 
public class Main {
    public static int findMax(int[] arr, int n)
    {
        Stack<Integer> s = new Stack<>();
        int max = 0;
 
        // traverse the array from left to right
        for (int i = 0; i < n; i++) {
            // push the index onto the stack if the element
            // is less than or equal to the previous element
            if (s.empty() || arr[i] <= arr[s.peek()]) {
                s.push(i);
            }
            else {
                // pop all the indices from the stack until
                // we find an index whose corresponding
                // element is greater than the current
                // element
                while (!s.empty()
                       && arr[i] > arr[s.peek()]) {
                    int index = s.peek();
                    s.pop();
                    // update the maximum element
                    if (arr[index] > max) {
                        max = arr[index];
                    }
                }
                // push the current index onto the stack
                s.push(i);
            }
        }
 
        // the maximum element is the element corresponding
        // to the last index remaining on the stack
        while (!s.empty()) {
            int index = s.peek();
            s.pop();
            if (arr[index] > max) {
                max = arr[index];
            }
        }
 
        return max;
    }
 
    public static void main(String[] args)
    {
        int[] arr = { 1, 3, 50, 10, 9, 7, 6 };
        int n = arr.length;
        System.out.println("The maximum element is "
                           + findMax(arr, n));
    }
}

Python3

def findMax(arr, n):
    s = []
    max = 0
 
    # traverse the array from left to right
    for i in range(n):
       
        # push the index onto the stack if the element is
        # less than or equal to the previous element
        if not s or arr[i] <= arr[s[-1]]:
            s.append(i)
        else:
            # pop all the indices from the stack until we
            # find an index whose corresponding element is
            # greater than the current element
            while s and arr[i] > arr[s[-1]]:
                index = s.pop()
                # update the maximum element
                if arr[index] > max:
                    max = arr[index]
            # push the current index onto the stack
            s.append(i)
 
    # the maximum element is the element corresponding to
    # the last index remaining on the stack
    while s:
        index = s.pop()
        if arr[index] > max:
            max = arr[index]
 
    return max
 
 
arr = [1, 3, 50, 10, 9, 7, 6]
n = len(arr)
print("The maximum element is", findMax(arr, n))

C#

// C# program to find maximum element
using System;
using System.Collections.Generic;
 
class GFG
{
    static int FindMax(int[] arr, int n)
    {
        Stack<int> stack = new Stack<int>();
        int max = 0;
 
        // Traverse the array from left to right
        for (int i = 0; i < n; i++)
        {
            // Push the index onto the stack if the element is
            // less than or equal to the previous element
            if (stack.Count == 0 || arr[i] <= arr[stack.Peek()])
            {
                stack.Push(i);
            }
            else
            {
                // Pop all the indices from the stack until we
                // find an index whose corresponding element is
                // greater than the current element
                while (stack.Count > 0 && arr[i] > arr[stack.Peek()])
                {
                    int index = stack.Pop();
                    // Update the maximum element
                    if (arr[index] > max)
                    {
                        max = arr[index];
                    }
                }
                // Push the current index onto the stack
                stack.Push(i);
            }
        }
 
        // The maximum element is the element corresponding to
        // the last index remaining on the stack
        while (stack.Count > 0)
        {
            int index = stack.Pop();
            if (arr[index] > max)
            {
                max = arr[index];
            }
        }
 
        return max;
    }
//Driver Code
    static void Main()
    {
        int[] arr = { 1, 3, 50, 10, 9, 7, 6 };
        int n = arr.Length;
        Console.WriteLine("The maximum element is " + FindMax(arr, n));
    }
}

Javascript

function findMax(arr) {
    const stack = []; // Create an array to simulate the stack
    let max = 0; // Variable to store the maximum element found
 
    // Traverse the array from left to right
    for (let i = 0; i < arr.length; i++) {
        // Push the index onto the stack if the element is less than or equal to the previous element
        if (stack.length === 0 || arr[i] <= arr[stack[stack.length - 1]]) {
            stack.push(i);
        } else {
            // Pop all the indices from the stack until we find an index whose corresponding element is greater than the current element
            while (stack.length > 0 && arr[i] > arr[stack[stack.length - 1]]) {
                const index = stack.pop();
                // Update the maximum element if the element at the popped index is greater than the current max
                if (arr[index] > max) {
                    max = arr[index];
                }
            }
            // Push the current index onto the stack
            stack.push(i);
        }
    }
 
    // After processing all elements, there may be remaining indices on the stack.
    // These indices correspond to elements that are greater than any elements to their right.
    // We need to check these elements and update the max value if necessary.
    while (stack.length > 0) {
        const index = stack.pop();
        if (arr[index] > max) {
            max = arr[index];
        }
    }
 
    return max;
}
 
// Driver code
const arr = [1, 3, 50, 10, 9, 7, 6];
console.log("The maximum element is " + findMax(arr));

Output

The maximum element is 50

Time Complexity : O(n)
Auxiliary Space : O(n)

GeeksforGeeks

Improve

Floor in a Sorted Array

Given Array of size n and a number k, find all elements that appear more than n/k times

Most Common Searching Algorithms

Other Searching Algorithms

Comparisons between Searching Algorithms

Library implementations of Searching algorithms

Easy problems on Searching algorithms

Medium problems on Searching algorithms

Hard problems on Searching algorithms

Find the maximum element in an array which is first increasing and then decreasing

C++

C

Java

Python3

C#

Javascript

PHP

C++

C

Java

Python3

C#

Javascript

PHP

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

Please Login to comment...

Similar Reads

What kind of Experience do you want to share?