Dada una array de enteros que inicialmente es creciente y luego decreciente, encuentre el valor máximo en la array.
Ejemplos:
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
Método 1 (búsqueda lineal) : podemos recorrer la array y realizar un seguimiento del máximo y el elemento. Y finalmente devolver el elemento máximo.
Implementación:
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>
Producción
The maximum element is 70
Complejidad de tiempo : O(n)
Espacio Auxiliar : O(1)
Método 2 (búsqueda binaria) :
Podemos modificar el algoritmo de búsqueda binaria estándar para el tipo dado de arrays.
- Si el elemento medio es mayor que sus dos elementos adyacentes, entonces medio es el máximo.
- Si el elemento medio es mayor que su siguiente elemento y menor que el elemento anterior, el máximo se encuentra en el lado izquierdo de la mitad. Array de ejemplo: {3, 50, 10, 9, 7, 6}
- Si el elemento medio es más pequeño que su siguiente elemento y mayor que el elemento anterior, el máximo se encuentra en el lado derecho de la mitad. Array de ejemplo: {2, 4, 6, 8, 10, 3, 1}
Implementación:
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" + "\n" + findMaximum(arr, 0, n-1));
// This code is contributed by simranarora5sos
</script>
Producción
The maximum element is 50
Complejidad de tiempo: O (logn)
Espacio auxiliar : O(logn)
Este método funciona solo para números distintos. Por ejemplo, no funcionará para una array como {0, 1, 1, 2, 2, 2, 2, 2, 3, 4, 4, 5, 3, 3, 2, 2, 1, 1}.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Método 3 (Búsqueda binaria – Solución iterativa)
El enfoque iterativo de la búsqueda binaria para encontrar el elemento máximo en una array que primero aumenta y luego disminuye.
Podemos modificar el algoritmo de búsqueda binaria estándar para el tipo dado de arrays.
- Si el elemento medio es mayor que sus dos elementos adyacentes, entonces medio es el máximo.
- Si el elemento medio es mayor que su siguiente elemento y menor que el elemento anterior, el máximo se encuentra en el lado izquierdo de la mitad. Array de ejemplo: {3, 50, 10, 9, 7, 6}
- Si el elemento medio es más pequeño que su siguiente elemento y mayor que el elemento anterior, el máximo se encuentra en el lado derecho de la mitad. Array de ejemplo: {2, 4, 6, 8, 10, 3, 1}
Implementación:
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(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
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(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>
Producción
The maximum element is 50
Complejidad de tiempo: O (log n)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA