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

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

## 本文概述

``````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``````

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

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
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``