Рубрики

Найти максимальный элемент в массиве, который сначала увеличивается, а затем уменьшается

Учитывая массив целых чисел, который первоначально увеличивается, а затем уменьшается, найдите максимальное значение в массиве.
Примеры :

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 ++ программа для поиска максимума
// элемент
#include <bits/stdc++.h>

using namespace std;

  
// функция для поиска максимального элемента

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]; 

          

        // разрыв, когда элемент меньше чем

        // макс тогда он будет уменьшаться

        // и после этого проверять не нужно

        else

            break

    

    return max; 

  
/ * Код водителя * /

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; 

  
// Это код, предоставленный rathbhupendra

С

// C программа для поиска максимума
// элемент
#include <stdio.h>

  
// функция для поиска максимального элемента

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];

// разрыв, когда элемент меньше чем
// макс тогда он будет уменьшаться
// и после этого проверять не нужно

    else

        break;

}

return max;

}

  
/ * Программа драйвера для проверки вышеуказанных функций * /

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-программа, чтобы найти максимум
// элемент

  

class Main

{   

    // функция для поиска

    // максимальный элемент

    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;

    }

      

    // основная функция

    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 программа для поиска
# максимальный элемент

  

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

  
# Драйверная программа для проверки вышеуказанных функций * /

arr = [1, 30, 40, 50, 60, 70, 23, 20]

n = len(arr)

print ("The maximum element is %d"% 

        findMaximum(arr, 0, n-1))

  
# Этот код предоставлен Shreyanshi Arun.

C #

// C # программа для поиска максимума
// элемент

using System;

  

class GFG

{

    // функция для поиска

    // максимальный элемент

    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;

    }

      

    // Код драйвера

    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));

    }

}

  
// Этот код предоставлен Sam007

PHP

<?php
// PHP программа для поиска максимума
// элемент в массиве, который является первым
// увеличиваем, а затем уменьшаем

  

function findMaximum($arr, $low, $high)

{

$max = $arr[$low];

$i;

for ($i = $low; $i <= $high; $i++)

{

    if ($arr[$i] > $max)

        $max = $arr[$i];

}

return $max;

}

  
// Код драйвера

$arr = array(1, 30, 40, 50, 

             60, 70, 23, 20);

$n = count($arr);

echo "The maximum element is "

      findMaximum($arr, 0, $n-1);

  
// Этот код предоставлен anuj_67.
?>


Выход :

The maximum element is 70

Сложность времени: O (n)

Метод 2 (бинарный поиск)
Мы можем изменить стандартный алгоритм бинарного поиска для данного типа массивов.
i) Если средний элемент больше, чем оба смежных элемента, то средний является максимумом.
ii) Если средний элемент больше, чем его следующий элемент и меньше, чем предыдущий элемент, то максимум находится слева от середины. Пример массива: {3, 50, 10, 9, 7, 6}
iii) Если средний элемент меньше, чем его следующий элемент и больше, чем предыдущий элемент, то максимум находится справа от середины. Пример массива: {2, 4, 6, 8, 10, 3, 1}

C ++

#include <bits/stdc++.h>

using namespace std;

  

int findMaximum(int arr[], int low, int high) 

  

    / * Базовый регистр: в arr [low..high] * присутствует только один элемент

    if (low == high) 

        return arr[low]; 

      

    / * Если есть два элемента и первый больше, то

        первый элемент максимальный * /

    if ((high == low + 1) && arr[low] >= arr[high]) 

        return arr[low]; 

      

    / * Если есть два элемента, а второй больше, то

        второй элемент максимальный * /

    if ((high == low + 1) && arr[low] < arr[high]) 

        return arr[high]; 

      

    int mid = (low + high)/2; / * низкий + (высокий - низкий) / 2; * /

      

    / * Если мы достигнем точки, где arr [mid] больше, чем оба

        смежные элементы arr [mid-1] и arr [mid + 1], затем arr [mid]

        это максимальный элемент * /

    if ( arr[mid] > arr[mid + 1] && arr[mid] > arr[mid - 1]) 

        return arr[mid]; 

      

    / * Если arr [mid] больше следующего

        элемент и меньше, чем предыдущий

        элемент тогда максимум лежит слева от середины * /

    if (arr[mid] > arr[mid + 1] && arr[mid] < arr[mid - 1]) 

        return findMaximum(arr, low, mid-1); 

          

        // когда arr [mid] больше, чем arr [mid-1]

        // и меньше, чем arr [mid + 1]

    else 

        return findMaximum(arr, mid + 1, high); 

  
/ * Код водителя * /

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; 

  
// Это код, предоставленный rathbhupendra

С

#include <stdio.h>

  

int findMaximum(int arr[], int low, int high)

{

  

   / * Базовый регистр: в arr [low..high] * присутствует только один элемент

   if (low == high)

     return arr[low];

  

   / * Если есть два элемента и первый больше, то

      первый элемент максимальный * /

   if ((high == low + 1) && arr[low] >= arr[high])

      return arr[low];

  

   / * Если есть два элемента, а второй больше, то

      второй элемент максимальный * /

   if ((high == low + 1) && arr[low] < arr[high])

      return arr[high];

  

   int mid = (low + high)/2;   / * низкий + (высокий - низкий) / 2; * /

  

   / * Если мы достигнем точки, где arr [mid] больше, чем оба

     смежные элементы arr [mid-1] и arr [mid + 1], затем arr [mid]

     это максимальный элемент * /

   if ( arr[mid] > arr[mid + 1] && arr[mid] > arr[mid - 1])

      return arr[mid];

  

   / * Если arr [mid] больше следующего элемента и меньше предыдущего

    элемент тогда максимум лежит слева от середины * /

   if (arr[mid] > arr[mid + 1] && arr[mid] < arr[mid - 1])

     return findMaximum(arr, low, mid-1);

   else // когда arr [mid] больше, чем arr [mid-1] и меньше, чем arr [mid + 1]

     return findMaximum(arr, mid + 1, high);

}

  
/ * Программа драйвера для проверки вышеуказанных функций * /

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-программа, чтобы найти максимум
// элемент

  

class Main

{   

    // функция для поиска

    // максимальный элемент

    static int findMaximum(int arr[], int low, int high)

    {

       

       / * Базовый случай: только один элемент

          присутствует в arr [low..high] * /

       if (low == high)

         return arr[low];

       

       / * Если есть два элемента и

          первый больше первого

          элемент максимальный * /

       if ((high == low + 1) && arr[low] >= arr[high])

          return arr[low];

       

       / * Если есть два элемента и

          второй больше второго

          элемент максимальный * /

       if ((high == low + 1) && arr[low] < arr[high])

          return arr[high];

          

       / * низкий + (высокий - низкий) / 2; * /

       int mid = (low + high)/2;   

       

       / * Если мы достигнем точки, где arr [mid]

          больше, чем оба соседних

          элементы arr [mid-1] и arr [mid + 1],

          тогда arr [mid] - максимальный элемент * /

       if ( arr[mid] > arr[mid + 1] && arr[mid] > arr[mid - 1])

          return arr[mid];

       

       / * Если arr [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);

    }

      

    // основная функция

    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):

    # Базовый случай: в arr [low..high] * / присутствует только один элемент

    if low == high:

        return arr[low]

   

    # Если есть два элемента и первый больше, то

    # первый элемент максимальный * /

    if high == low + 1 and arr[low] >= arr[high]:

        return arr[low];

   

    # Если есть два элемента, а второй больше, то

    # второй элемент максимальный * /

    if high == low + 1 and arr[low] < arr[high]:

        return arr[high]

   

    mid = (low + high)//2   #low + (высокий - низкий) / 2; * /

   

    # Если мы достигнем точки, где arr [mid] больше, чем оба

    # смежные элементы arr [mid-1] и arr [mid + 1], затем arr [mid]

    # - максимальный элемент * /

    if arr[mid] > arr[mid + 1] and arr[mid] > arr[mid - 1]:

        return arr[mid]

   

    # Если arr [mid] больше следующего элемента и меньше предыдущего

    # элемент, тогда максимум лежит слева от середины * /

    if arr[mid] > arr[mid + 1] and arr[mid] < arr[mid - 1]:

        return findMaximum(arr, low, mid-1)

    else: # когда arr [mid] больше, чем arr [mid-1] и меньше, чем arr [mid + 1]

        return findMaximum(arr, mid + 1, high)

   
# Драйверная программа для проверки вышеуказанных функций * /

arr = [1, 3, 50, 10, 9, 7, 6]

n = len(arr)

print ("The maximum element is %d"% findMaximum(arr, 0, n-1))

  
# Этот код предоставлен Shreyanshi Arun.

C #

// C # программа для поиска максимума
// элемент

using System;

  

class GFG

{

    // функция для поиска

    // максимальный элемент

    static int findMaximum(int []arr, int low, int high)

    {

      

    / * Базовый случай: только один элемент

        присутствует в arr [low..high] * /

    if (low == high)

        return arr[low];

      

    / * Если есть два элемента и

        первый больше первого

        элемент максимальный * /

    if ((high == low + 1) && arr[low] >= arr[high])

        return arr[low];

      

    / * Если есть два элемента и

        второй больше второго

        элемент максимальный * /

    if ((high == low + 1) && arr[low] < arr[high])

        return arr[high];

          

    / * низкий + (высокий - низкий) / 2; * /

    int mid = (low + high)/2; 

      

    / * Если мы достигнем точки, где arr [mid]

        больше, чем оба соседних

        элементы arr [mid-1] и arr [mid + 1],

        тогда arr [mid] - максимальный элемент * /

    if ( arr[mid] > arr[mid + 1] && arr[mid] > arr[mid - 1])

        return arr[mid];

      

    / * Если arr [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);

    }

      

    // основная функция

    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));

    }

}
// Этот код предоставлен Sam007

PHP

<?php
// PHP программа для поиска максимума
// элемент в массиве
// сначала увеличиваем, а затем уменьшаем

  

function findMaximum($arr, $low, $high)

{

  

    / * Базовый случай: только один элемент

       присутствует в arr [low..high] * /

    if ($low == $high)

        return $arr[$low];

      

    / * Если есть два элемента

       и сначала больше, чем потом

       первый элемент максимальный * /

    if (($high == $low + 1) && 

        $arr[$low] >= $arr[$high])

        return $arr[$low];

      

    / * Если есть два элемента

       а второй больше, чем

       второй элемент максимальный * /

    if (($high == $low + 1) && 

         $arr[$low] < $arr[$high])

        return $arr[$high];

      

    / * низкий + (высокий - низкий) / 2; * /

    $mid = ($low + $high) / 2; 

      

    / * Если мы достигнем точки, где

       arr [mid] больше чем

       оба его смежных элемента

       обр [середина 1] и обр [середина + 1],

       тогда arr [mid] - максимум

       элемент * /

    if ( $arr[$mid] > $arr[$mid + 1] &&

         $arr[$mid] > $arr[$mid - 1])

        return $arr[$mid];

      

    / * Если arr [mid] больше чем

       следующий элемент и меньше

       чем предыдущий элемент тогда

       максимум лежит на левой стороне середины * /

    if ($arr[$mid] > $arr[$mid + 1] && 

        $arr[$mid] < $arr[$mid - 1])

        return findMaximum($arr, $low, $mid - 1);

      

    // когда arr [mid] больше чем

    // arr [mid-1] и меньше чем

    // arr [mid + 1]

    else 

        return findMaximum($arr

                           $mid + 1, $high);

}

  
// Код драйвера

$arr = array(1, 3, 50, 10, 9, 7, 6);

$n = sizeof($arr);

echo("The maximum element is "); 

echo(findMaximum($arr, 0, $n-1));

  
// Этот код предоставлен нитин митталь.
?>


Выход :

The maximum element is 50

Сложность времени: O (Logn)

Этот метод работает только для разных чисел. Например, он не будет работать для таких массивов, как {0, 1, 1, 2, 2, 2, 2, 2, 3, 4, 4, 5, 3, 3, 2, 2, 1, 1}.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Найти максимальный элемент в массиве, который сначала увеличивается, а затем уменьшается

0.00 (0%) 0 votes