算法：在先增加然后减少的数组中找到最大元素

2021年3月30日15:39:06 发表评论 695 次浏览

本文概述

给定一个整数数组, 该数组最初是递增的, 然后递减的, 请在该数组中找到最大值。

例子 ：

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

推荐：请在"实践首先, 在继续解决方案之前。

方法1(线性搜索)

我们可以遍历数组并跟踪最大值和元素。最后返回最大元素。

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

的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.
?>

输出：

The maximum element is 70

时间复杂度：上)

方法2(二进制搜索)

我们可以为给定类型的数组修改标准的二进制搜索算法。

i)如果mid元素大于其两个相邻元素, 则mid是最大值。

ii)如果mid元素大于其下一个元素且小于前一个元素, 则最大值位于mid的左侧。数组示例：{3, 50, 10, 9, 7, 6}

iii)如果mid元素小于其下一个元素且大于前一个元素, 则最大值位于mid的右侧。数组示例：{2, 4, 6, 8, 8, 10, 3, 1}

C ++

#include <bits/stdc++.h>
using namespace std;
  
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 then 
         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 then 
         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); 
          
         // when arr[mid] is greater than arr[mid-1]
         // and smaller than arr[mid+1]
     else 
         return findMaximum(arr, mid + 1, high); 
} 
  
/* 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 rathbhupendra

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 then
       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 then
       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 then 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 then 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 then
     # 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 then
     # 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 then 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 then 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

的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 then
        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 then
        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.
?>

输出：

The maximum element is 50

时间复杂度：O(Log n)

此方法仅适用于不同的数字。例如, 它不适用于{0, 1, 1, 2, 2, 2, 2, 2, 2, 4, 4, 4, 5, 3, 3, 2, 2, 1, 1}这样的数组。

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: