给定一个整数数组，先递增后递减，找出数组中的最大值。 例如：
null
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. ?> |
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> |
输出
The maximum element is 70
时间复杂性： O（n） 方法2（二进制搜索） 我们可以修改给定类型数组的标准二进制搜索算法。 i） 如果中间元素大于其两个相邻元素，则中间元素为最大值。 ii）如果mid元素大于下一个元素且小于上一个元素，则最大值位于mid的左侧。示例数组：{3,50,10,9,7,6} iii）如果mid元素小于下一个元素且大于上一个元素，则最大值位于mid的右侧。示例数组：{2,4,6,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. ?> |
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 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]; 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" + "" + findMaximum(arr, 0, n-1)); // This code is contributed by simranarora5sos </script> |
输出
The maximum element is 50
时间复杂性： O（Logn） 此方法仅适用于不同的数字。例如，它不适用于{0，1，1，2，2，2，2，3，4，4，5，3，3，2，2，1，1}这样的数组。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
方法3 （二进制搜索-迭代解）
二元搜索的迭代方法，在一个先增加后减少的数组中寻找最大元素。
我们可以修改给定类型数组的标准二进制搜索算法。
i） 如果中间元素大于其两个相邻元素，则中间元素为最大值。
ii）如果中间元件大于下一个元件且小于上一个元件，则最大值位于中间元件左侧。
示例数组：{3,50,10,9,7,6}
iii）如果mid元素小于下一个元素且大于上一个元素，则最大值位于mid的右侧。示例数组：{2,4,6,8,10,3,1}
C++
#include <iostream> using namespace std; 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 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 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; } |
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 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 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 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 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> |
输出
The maximum element is 50
时间复杂性： O（对数n） 辅助空间： O（1）
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
