Рубрики

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

Учитывая массив arr [] целых чисел, определите максимальную разницу между любыми двумя элементами, чтобы больший элемент появлялся после меньшего числа.

Примеры :

Input : arr = {2, 3, 10, 6, 4, 8, 1}
Output : 8
Explanation : The maximum difference is between 10 and 2.

Input : arr = {7, 9, 5, 6, 3, 2}
Output : 2
Explanation : The maximum difference is between 9 and 7.

Способ 1 (простой)
Используйте две петли. Во внешнем цикле выбирают элементы один за другим, а во внутреннем цикле вычисляют разницу между выбранным элементом и каждым другим элементом в массиве и сравнивают разницу с максимальной разницей, рассчитанной до сих пор. Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ программа для поиска максимальной разницы
// между двумя элементами, такими, что больше
// элемент появляется после меньшего номера
#include <bits/stdc++.h>

using namespace std;

  
/ * Функция предполагает, что есть

   как минимум два элемента в массиве.

   функция возвращает отрицательное значение, если

   массив сортируется в порядке убывания и

   возвращает 0, если элементы равны * /

int maxDiff(int arr[], int arr_size)

{     

  int max_diff = arr[1] - arr[0];

  for (int i = 0; i < arr_size; i++)

  {

    for (int j = i+1; j < arr_size; j++)

    {     

      if (arr[j] - arr[i] > max_diff) 

        max_diff = arr[j] - arr[i];

    

  }         

  return max_diff;

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

int main()

{

  int arr[] = {1, 2, 90, 10, 110};

  int n = sizeof(arr) / sizeof(arr[0]);

    

  // вызов функции

  cout << "Maximum difference is " << maxDiff(arr, n);

  

  return 0;

}

С

#include<stdio.h>

  
/ * Функция предполагает, что есть как минимум два

   элементы в массиве.

   Функция возвращает отрицательное значение, если массив

   отсортировано в порядке убывания.

   Возвращает 0, если элементы равны * /

int maxDiff(int arr[], int arr_size)

{     

  int max_diff = arr[1] - arr[0];

  int i, j;

  for (i = 0; i < arr_size; i++)

  {

    for (j = i+1; j < arr_size; j++)

    {        

      if (arr[j] - arr[i] > max_diff)   

         max_diff = arr[j] - arr[i];

    }    

  }          

  return max_diff;

}    

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

int main()

{

  int arr[] = {1, 2, 90, 10, 110};

  printf("Maximum difference is %d",  maxDiff(arr, 5));

  getchar();

  return 0;

}

Джава

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

class MaximumDiffrence 

{

    / * Функция предполагает, что есть как минимум два

       элементы в массиве.

       Функция возвращает отрицательное значение, если массив

       отсортировано в порядке убывания.

       Возвращает 0, если элементы равны * /

    int maxDiff(int arr[], int arr_size) 

    {

        int max_diff = arr[1] - arr[0];

        int i, j;

        for (i = 0; i < arr_size; i++) 

        {

            for (j = i + 1; j < arr_size; j++) 

            {

                if (arr[j] - arr[i] > max_diff)

                    max_diff = arr[j] - arr[i];

            }

        }

        return max_diff;

    }

  

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

    public static void main(String[] args) 

    {

        MaximumDiffrence maxdif = new MaximumDiffrence();

        int arr[] = {1, 2, 90, 10, 110};

        System.out.println("Maximum differnce is "

                                maxdif.maxDiff(arr, 5));

    }

}

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

python3

# Код Python 3 для поиска максимальной разницы
# между двумя элементами, так что больше
Элемент # появляется после меньшего номера

  
# Функция предполагает, что есть в
# минимум два элемента в массиве. Функция
# возвращает отрицательное значение, если массив
# отсортировано в порядке убывания. Возвращает 0
# если элементы равны

def maxDiff(arr, arr_size):

    max_diff = arr[1] - arr[0]

      

    for i in range( 0, arr_size ):

        for j in range( i+1, arr_size ):

            if(arr[j] - arr[i] > max_diff): 

                max_diff = arr[j] - arr[i]

      

    return max_diff

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

arr = [1, 2, 90, 10, 110]

size = len(arr)

print ("Maximum difference is", maxDiff(arr, size))

  
# Этот код предоставлен Swetank Modi

C #

// код C # для поиска максимальной разницы

using System;

  

class GFG {

  

    // Функция предполагает, что

    // как минимум два элемента в массиве

    // Функция возвращает отрицательный

    // значение, если массив отсортирован в

    // убывающий порядок. Возвращает 0, если

    // элементы равны

    static int maxDiff(int[] arr, int arr_size)

    {

        int max_diff = arr[1] - arr[0];

        int i, j;

        for (i = 0; i < arr_size; i++) {

            for (j = i + 1; j < arr_size; j++) {

                if (arr[j] - arr[i] > max_diff)

                    max_diff = arr[j] - arr[i];

            }

        }

        return max_diff;

    }

  

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

    public static void Main()

    {

  

        int[] arr = { 1, 2, 90, 10, 110 };

        Console.Write("Maximum differnce is "

                                maxDiff(arr, 5));

    }

}

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

PHP

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

  
/ * Функция предполагает, что есть
как минимум два элемента в массиве.
функция возвращает отрицательное значение, если
массив сортируется в порядке убывания и
возвращает 0, если элементы равны * /

function maxDiff($arr, $arr_size)

$max_diff = $arr[1] - $arr[0];

for ($i = 0; $i < $arr_size; $i++)

{

    for ($j = $i+1; $j < $arr_size; $j++)

    

    if ($arr[$j] - $arr[$i] > $max_diff

        $max_diff = $arr[$j] - $arr[$i];

    

}     

return $max_diff;

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

$arr = array(1, 2, 90, 10, 110);

$n = sizeof($arr);

  
// вызов функции

echo "Maximum difference is "

             maxDiff($arr, $n);

  
// Этот код добавлен
// Аканкша Рай (Abby_akku)


Выход :

Maximum difference is 109

Сложность времени: O (n ^ 2)
Вспомогательное пространство: O (1)

Метод 2 (хитрый и эффективный)
В этом методе вместо разницы выбранного элемента с любым другим элементом мы берем разницу с минимальным найденным элементом. Итак, нам нужно отслеживать 2 вещи:
1) Максимальная найденная разница (max_diff).
2) Минимальное количество посещенных до сих пор (min_element).

C ++

// C ++ программа для поиска максимальной разницы
// между двумя элементами, такими, что больше
// элемент появляется после меньшего номера
#include <bits/stdc++.h>

using namespace std;

  
/ * Функция предполагает, что есть

   как минимум два элемента в массиве.

   функция возвращает отрицательное значение, если

   массив сортируется в порядке убывания и

   возвращает 0, если элементы равны * /

int maxDiff(int arr[], int arr_size)

{

     // Максимальная разница найдена

     int max_diff = arr[1] - arr[0];

       

     // Минимальное количество посещенных к настоящему времени

     int min_element = arr[0];

     for(int i = 1; i < arr_size; i++)

     {     

       if (arr[i] - min_element > max_diff)                             

       max_diff = arr[i] - min_element;

         

       if (arr[i] < min_element)

       min_element = arr[i];                     

     }

       

     return max_diff;

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

int main()

{

  int arr[] = {1, 2, 90, 10, 110};

  int n = sizeof(arr) / sizeof(arr[0]);

    

  // вызов функции

  cout << "Maximum difference is " << maxDiff(arr, n);

  

  return 0;

}

С

#include<stdio.h>

  
/ * Функция предполагает, что есть как минимум два
элементы в массиве.
Функция возвращает отрицательное значение, если массив
отсортировано в порядке убывания.
Возвращает 0, если элементы равны * /

int maxDiff(int arr[], int arr_size)

{

int max_diff = arr[1] - arr[0];

int min_element = arr[0];

int i;

for(i = 1; i < arr_size; i++)

{     

    if (arr[i] - min_element > max_diff)                             

    max_diff = arr[i] - min_element;

    if (arr[i] < min_element)

        min_element = arr[i];                     

}

return max_diff;

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

int main()

{

int arr[] = {1, 2, 6, 80, 100};

int size = sizeof(arr)/sizeof(arr[0]);

printf("Maximum difference is %d", maxDiff(arr, size));

getchar();

return 0;

}

Джава

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

class MaximumDiffrence 

{

    / * Функция предполагает, что есть как минимум два

       элементы в массиве.

       Функция возвращает отрицательное значение, если массив

       отсортировано в порядке убывания.

       Возвращает 0, если элементы равны * /

    int maxDiff(int arr[], int arr_size) 

    {

        int max_diff = arr[1] - arr[0];

        int min_element = arr[0];

        int i;

        for (i = 1; i < arr_size; i++) 

        {

            if (arr[i] - min_element > max_diff)

                max_diff = arr[i] - min_element;

            if (arr[i] < min_element)

                min_element = arr[i];

        }

        return max_diff;

    }

  

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

    public static void main(String[] args) 

    {

        MaximumDiffrence maxdif = new MaximumDiffrence();

        int arr[] = {1, 2, 90, 10, 110};

        int size = arr.length;

        System.out.println("MaximumDifference is "

                                maxdif.maxDiff(arr, size));

    }

}

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

python3

# Код Python 3 для поиска максимальной разницы
# между двумя элементами, так что больше
Элемент # появляется после меньшего номера

  
# Функция предполагает, что есть
# как минимум два элемента в массиве.
# Функция возвращает отрицательный
# значение, если массив отсортирован в
# убывающий порядок. Возвращает 0, если
# элементы равны

def maxDiff(arr, arr_size):

    max_diff = arr[1] - arr[0]

    min_element = arr[0]

      

    for i in range( 1, arr_size ):

        if (arr[i] - min_element > max_diff):

            max_diff = arr[i] - min_element

      

        if (arr[i] < min_element):

            min_element = arr[i]

    return max_diff

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

arr = [1, 2, 6, 80, 100]

size = len(arr)

print ("Maximum difference is"

        maxDiff(arr, size))

  
# Этот код предоставлен Swetank Modi

C #

// код C # для поиска максимальной разницы

using System;

  

class GFG {

      

    // Функция предполагает, что

    // как минимум два элемента в массиве

    // Функция возвращает отрицательный

    // значение, если массив отсортирован в

    // убывающий порядок. Возвращает 0, если

    // элементы равны

    static int maxDiff(int[] arr, int arr_size)

    {

        int max_diff = arr[1] - arr[0];

        int min_element = arr[0];

        int i;

        for (i = 1; i < arr_size; i++) {

            if (arr[i] - min_element > max_diff)

                max_diff = arr[i] - min_element;

            if (arr[i] < min_element)

                min_element = arr[i];

        }

        return max_diff;

    }

  

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

    public static void Main()

    {

        int[] arr = { 1, 2, 90, 10, 110 };

        int size = arr.Length;

        Console.Write("MaximumDifference is " +

                               maxDiff(arr, size));

    }

}

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

PHP

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

  
// Функция предполагает, что
// как минимум два элемента в массиве
// Функция возвращает отрицательный
// значение, если массив отсортирован в
// убывает порядок и возвращает 0
// если элементы равны

function maxDiff($arr, $arr_size)

{

    // Максимальная разница найдена

    $max_diff = $arr[1] - $arr[0];

      

    // Минимальное количество посещенных к настоящему времени

    $min_element = $arr[0];

    for($i = 1; $i < $arr_size; $i++)

    {     

    if ($arr[$i] - $min_element > $max_diff)                             

    $max_diff = $arr[$i] - $min_element;

          

    if ($arr[$i] < $min_element)

    $min_element = $arr[$i];                     

    }

      

    return $max_diff;

}

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

$arr = array(1, 2, 90, 10, 110);

$n = count($arr);

  
// вызов функции

echo "Maximum difference is " .

             maxDiff($arr, $n);

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


Выход:

Maximum difference is 109

Сложность времени: O (n)
Вспомогательное пространство: O (1)

Как и элемент min, мы также можем отслеживать элемент max с правой стороны. Спасибо Катамарану за предложенный подход. Ниже приведена реализация:

C ++

// C ++ программа для поиска максимальной разницы
// между двумя элементами, такими, что больше
// элемент появляется после меньшего номера
#include <bits/stdc++.h>

using namespace std;

  
/ * Функция предполагает, что есть

   как минимум два элемента в массиве.

   функция возвращает отрицательное значение, если

   массив сортируется в порядке убывания и

   возвращает 0, если элементы равны * /

int maxDiff(int arr[], int n)

{

    // Инициализировать результат

    int maxDiff = -1; 

      

    // Инициализируем элемент max с правой стороны

    int maxRight = arr[n-1]; 

  

    for (int i = n-2; i >= 0; i--)

    {

        if (arr[i] > maxRight)

            maxRight = arr[i];

        else

        {

            int diff = maxRight - arr[i];

            if (diff > maxDiff)

            {

                maxDiff = diff;

            }

        }

    }

    return maxDiff;

}

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

int main()

{

  int arr[] = {1, 2, 90, 10, 110};

  int n = sizeof(arr) / sizeof(arr[0]);

    

  // вызов функции

  cout << "Maximum difference is " << maxDiff(arr, n);

  

  return 0;

}

Джава

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

  

import java.io.*;

  

class GFG {

/ * Функция предполагает, что есть
как минимум два элемента в массиве.
функция возвращает отрицательное значение, если
массив сортируется в порядке убывания и
возвращает 0, если элементы равны * /

static int maxDiff(int arr[], int n)

{

    // Инициализировать результат

    int maxDiff = -1

      

    // Инициализируем элемент max с правой стороны

    int maxRight = arr[n-1]; 

  

    for (int i = n-2; i >= 0; i--)

    {

        if (arr[i] > maxRight)

            maxRight = arr[i];

        else

        {

            int diff = maxRight - arr[i];

            if (diff > maxDiff)

            {

                maxDiff = diff;

            }

        }

    }

    return maxDiff;

}

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

    public static void main (String[] args) {

        int arr[] = {1, 2, 90, 10, 110};

        int n = arr.length;

  
// вызов функции

    System.out.println ("Maximum difference is " + maxDiff(arr, n));

    }

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

python3

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

  
# Функция предполагает, что есть
# как минимум два элемента в массиве.
Функция # возвращает отрицательное значение, если
# массив отсортирован в порядке убывания и
# возвращает 0, если элементы равны

def maxDiff(arr, n):

      

    # Initialize Result

    maxDiff = -1

      

    # Инициализировать элемент max из

    # правая сторона

    maxRight = arr[n - 1

  

    for i in range(n - 2, -1, -1):

        if (arr[i] > maxRight):

            maxRight = arr[i]

        else:

            diff = maxRight - arr[i]

            if (diff > maxDiff):

                maxDiff = diff

    return maxDiff

  
Код водителя

if __name__ == '__main__':

    arr = [1, 2, 90, 10, 110]

    n = len(arr)

      

    # Вызов функции

    print("Maximum difference is",

                  maxDiff(arr, n))

  
# Этот код предоставлен 29AjayKumar

C #

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

using System;

  

class GFG

{
/ * Функция предполагает, что есть
как минимум два элемента в массиве.
функция возвращает отрицательное значение, если
массив сортируется в порядке убывания и
возвращает 0, если элементы равны * /

static int maxDiff(int[] arr, int n)

{

    // Инициализировать результат

    int maxDiff = -1; 

      

    // Инициализируем элемент max с правой стороны

    int maxRight = arr[n-1]; 

  

    for (int i = n-2; i >= 0; i--)

    {

        if (arr[i] > maxRight)

            maxRight = arr[i];

        else

        {

            int diff = maxRight - arr[i];

            if (diff > maxDiff)

            {

                maxDiff = diff;

            }

        }

    }

    return maxDiff;

}

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

public static void Main () 

{

    int[] arr = {1, 2, 90, 10, 110};

    int n = arr.Length;

  

    // вызов функции

    Console.WriteLine("Maximum difference is "

                               maxDiff(arr, n));

}
}

  
// Этот код добавлен
// Аканкша Рай

PHP

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

  
/ * Функция предполагает, что есть
как минимум два элемента в массиве.
функция возвращает отрицательное значение, если
массив сортируется в порядке убывания и
возвращает 0, если элементы равны * /

function maxDiff($arr, $n

    // Инициализировать результат

    $maxDiff = -1; 

      

    // Инициализируем элемент max из

    // правая сторона

    $maxRight = $arr[$n - 1]; 

  

    for ($i = $n - 2; $i >= 0; $i--) 

    

        if ($arr[$i] > $maxRight

            $maxRight = $arr[$i]; 

        else

        

            $diff = $maxRight - $arr[$i]; 

            if ($diff > $maxDiff

            

                $maxDiff = $diff

            

        

    

    return $maxDiff

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

$arr = array(1, 2, 90, 10, 110); 

$n = sizeof($arr); 

      
// вызов функции

echo "Maximum difference is ",

            maxDiff($arr, $n); 

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

Выход:

Maximum difference is 109

Метод 3 (Другое хитрое решение)
Сначала найдите разницу между соседними элементами массива и сохраните все различия во вспомогательном массиве diff [] размера n-1. Теперь эта проблема превращается в поиск максимальной суммы подмассива этого массива разностей. Спасибо Шубхам Миттал за предложенное решение. Ниже приведена реализация:

C ++

// C ++ программа для поиска максимальной разницы
// между двумя элементами, такими, что больше
// элемент появляется после меньшего номера
#include <bits/stdc++.h>

using namespace std;

  
/ * Функция предполагает, что есть

   как минимум два элемента в массиве.

   функция возвращает отрицательное значение, если

   массив сортируется в порядке убывания и

   возвращает 0, если элементы равны * /

int maxDiff(int arr[], int n)

{

    // Создаем массив diff размером n-1.

    // Массив будет содержать разницу

    // соседних элементов

    int diff[n-1];

    for (int i=0; i < n-1; i++)

        diff[i] = arr[i+1] - arr[i];

  

    // Теперь найти максимальную сумму

    // подмассив в массиве diff

    int max_diff = diff[0];

    for (int i=1; i<n-1; i++)

    {

        if (diff[i-1] > 0)

            diff[i] += diff[i-1];

        if (max_diff < diff[i])

            max_diff = diff[i];

    }

    return max_diff;

}

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

int main()

{

  int arr[] = {80, 2, 6, 3, 100};

  int n = sizeof(arr) / sizeof(arr[0]);

    

  // вызов функции

  cout << "Maximum difference is " << maxDiff(arr, n);

  

  return 0;

}

С

#include<stdio.h>

  

int maxDiff(int arr[], int n)

{

    // Создаем массив diff размером n-1. Массив будет содержать

    // разница соседних элементов

    int diff[n-1];

    for (int i=0; i < n-1; i++)

        diff[i] = arr[i+1] - arr[i];

  

    // Теперь находим массив максимальной суммы в массиве diff

    int max_diff = diff[0];

    for (int i=1; i<n-1; i++)

    {

        if (diff[i-1] > 0)

            diff[i] += diff[i-1];

        if (max_diff < diff[i])

            max_diff = diff[i];

    }

    return max_diff;

}

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

int main()

{

    int arr[] = {80, 2, 6, 3, 100};

    int size = sizeof(arr)/sizeof(arr[0]);

    printf("Maximum difference is %d",  maxDiff(arr, size));

    return 0;

}

Джава

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

class MaximumDiffrence 

{

    int maxDiff(int arr[], int n) 

    {

        // Создаем массив diff размером n-1. Массив будет содержать

        // разница соседних элементов

        int diff[] = new int[n - 1];

        for (int i = 0; i < n - 1; i++)

            diff[i] = arr[i + 1] - arr[i];

  

        // Теперь находим массив максимальной суммы в массиве diff

        int max_diff = diff[0];

        for (int i = 1; i < n - 1; i++) 

        {

            if (diff[i - 1] > 0

                diff[i] += diff[i - 1];

            if (max_diff < diff[i])

                max_diff = diff[i];

        }

        return max_diff;

    }

  

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

    public static void main(String[] args) 

    {

        MaximumDiffrence mxdif = new MaximumDiffrence();

        int arr[] = {80, 2, 6, 3, 100};

        int size = arr.length;

        System.out.println(mxdif.maxDiff(arr, size));

    }

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

python3

# Код Python 3 для поиска максимальной разницы
# между двумя элементами, так что больше
Элемент # появляется после меньшего номера

  

def maxDiff(arr, n):

    diff = [0] * (n - 1)

    for i in range (0, n-1):

        diff[i] = arr[i+1] - arr[i]

          

    # Теперь найдите максимальную сумму

    # подмассив в массиве diff

    max_diff = diff[0]

    for i in range(1, n-1):

        if (diff[i-1] > 0):

            diff[i] += diff[i-1]

      

        if (max_diff < diff[i]):

            max_diff = diff[i]

      

    return max_diff

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

arr = [80, 2, 6, 3, 100]

size = len(arr)

print ("Maximum difference is"

       maxDiff(arr, size))

  
# Этот код предоставлен Swetank Modi

C #

// код C # для поиска максимальной разницы

using System;

  

class GFG {

    static int maxDiff(int[] arr, int n)

    {

          

        // Создаем массив diff размером n-1.

        // Массив будет содержать

        // разница соседних элементов

        int[] diff = new int[n - 1];

        for (int i = 0; i < n - 1; i++)

            diff[i] = arr[i + 1] - arr[i];

  

        // Теперь найти максимальную сумму

        // подмассив в массиве diff

        int max_diff = diff[0];

        for (int i = 1; i < n - 1; i++) {

            if (diff[i - 1] > 0)

                diff[i] += diff[i - 1];

            if (max_diff < diff[i])

                max_diff = diff[i];

        }

        return max_diff;

    }

  

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

    public static void Main()

    {

        int[] arr = { 80, 2, 6, 3, 100 };

        int size = arr.Length;

        Console.Write(maxDiff(arr, size));

    }

}

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

PHP

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

  
/ * Функция предполагает, что есть
как минимум два элемента в массиве.
функция возвращает отрицательное значение, если
массив сортируется в порядке убывания и
возвращает 0, если элементы равны * /

function maxDiff($arr, $n)

{

    // Создаем массив diff размером n-1.

    // Массив будет содержать разницу

    // соседних элементов

    $diff[$n-1] = array();

    for ($i=0; $i < $n-1; $i++)

        $diff[$i] = $arr[$i+1] - $arr[$i];

  

    // Теперь найти максимальную сумму

    // подмассив в массиве diff

    $max_diff = $diff[0];

    for ($i=1; $i<$n-1; $i++)

    {

        if ($diff[$i-1] > 0)

            $diff[$i] += $diff[$i-1];

        if ($max_diff < $diff[$i])

            $max_diff = $diff[$i];

    }

    return $max_diff;

}

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

$arr = array(80, 2, 6, 3, 100);

$n = sizeof($arr);

  
// вызов функции

echo "Maximum difference is "

             maxDiff($arr, $n);

  
// Этот код добавлен
// Аканкша Рай


Выход:

Maximum difference is 98

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

Мы можем модифицировать вышеуказанный метод для работы в O (1) дополнительном пространстве. Вместо создания вспомогательного массива мы можем вычислить diff и max sum в одном цикле. Ниже приводится оптимизированная для пространства версия.

C ++

// C ++ программа для поиска максимальной разницы
// между двумя элементами, такими, что больше
// элемент появляется после меньшего номера
#include <bits/stdc++.h>

using namespace std;

  
/ * Функция предполагает, что есть

   как минимум два элемента в массиве.

   функция возвращает отрицательное значение, если

   массив сортируется в порядке убывания и

   возвращает 0, если элементы равны * /

int maxDiff (int arr[], int n)

{

    // Инициализируем diff, текущую сумму и максимальную сумму

    int diff = arr[1]-arr[0];

    int curr_sum = diff;

    int max_sum = curr_sum;

  

    for(int i=1; i<n-1; i++)

    {

        // Рассчитать текущую разницу

        diff = arr[i+1]-arr[i];

  

        // Расчет текущей суммы

        if (curr_sum > 0)

        curr_sum += diff;

        else

        curr_sum = diff;

  

        // Обновить максимальную сумму, если необходимо

        if (curr_sum > max_sum)

        max_sum = curr_sum;

    }

  

    return max_sum;

}

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

int main()

{

  int arr[] = {80, 2, 6, 3, 100};

  int n = sizeof(arr) / sizeof(arr[0]);

    

  // вызов функции

  cout << "Maximum difference is " << maxDiff(arr, n);

  

  return 0;

}

Джава

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

class GFG

{

      
/ * Функция предполагает, что там
как минимум два элемента в массиве.
Функция возвращает отрицательный
значение, если массив отсортирован в
убывающий порядок и возвращает 0, если
элементы равны * /

static int maxDiff (int arr[], int n) 

    // Инициализируем diff, current

    // сумма и максимальная сумма

    int diff = arr[1] - arr[0]; 

    int curr_sum = diff; 

    int max_sum = curr_sum; 

  

    for(int i = 1; i < n - 1; i++) 

    

        // Рассчитать текущую разницу

        diff = arr[i + 1] - arr[i]; 

  

        // Расчет текущей суммы

        if (curr_sum > 0

        curr_sum += diff; 

        else

        curr_sum = diff; 

  

        // Обновить максимальную сумму, если необходимо

        if (curr_sum > max_sum) 

        max_sum = curr_sum; 

    

  

    return max_sum; 

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

public static void main(String[] args) 

int arr[] = {80, 2, 6, 3, 100}; 

int n = arr.length; 

      
// вызов функции

System.out.print("Maximum difference is "

                          maxDiff(arr, n)); 

}

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

python3

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

  
# Функция предполагает, что есть
# как минимум два элемента в массиве.
Функция # возвращает отрицательное значение, если
# массив отсортирован по убыванию
# order и возвращает 0, если элементы равны

def maxDiff (arr, n):

      

    # Инициализировать diff, current

    # сумма и максимальная сумма

    diff = arr[1] - arr[0]

    curr_sum = diff

    max_sum = curr_sum

  

    for i in range(1, n - 1):

          

        # Рассчитать текущую разницу

        diff = arr[i + 1] - arr[i]

  

        # Рассчитать текущую сумму

        if (curr_sum > 0):

            curr_sum += diff

        else:

            curr_sum = diff

  

        # Обновить максимальную сумму, если необходимо

        if (curr_sum > max_sum):

            max_sum = curr_sum

    return max_sum

  
Код водителя

if __name__ == '__main__':

    arr = [80, 2, 6, 3, 100]

    n = len(arr)

          

    # Вызов функции

    print("Maximum difference is",

                  maxDiff(arr, n))

  
# Этот код добавлен
# by 29AjayKumar

C #

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

using System;

class GFG

{

      
/ * Функция предполагает, что там
как минимум два элемента в массиве.
Функция возвращает отрицательный
значение, если массив отсортирован в
убывающий порядок и возвращает 0, если
элементы равны * /

static int maxDiff (int[] arr, int n) 

    // Инициализируем diff, current

    // сумма и максимальная сумма

    int diff = arr[1] - arr[0]; 

    int curr_sum = diff; 

    int max_sum = curr_sum; 

  

    for(int i = 1; i < n - 1; i++) 

    

        // Рассчитать текущую разницу

        diff = arr[i + 1] - arr[i]; 

  

        // Расчет текущей суммы

        if (curr_sum > 0) 

        curr_sum += diff; 

        else

        curr_sum = diff; 

  

        // Обновить максимальную сумму, если необходимо

        if (curr_sum > max_sum) 

        max_sum = curr_sum; 

    

  

    return max_sum; 

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

public static void Main() 

int[] arr = {80, 2, 6, 3, 100}; 

int n = arr.Length; 

      
// вызов функции

Console.WriteLine("Maximum difference is "

                        maxDiff(arr, n)); 

}

  
// Этот код добавлен
// Аканкша Рай (Abby_akku)

PHP

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

  
/ * Функция предполагает, что есть
как минимум два элемента в массиве.
функция возвращает отрицательное значение, если
массив сортируется в порядке убывания и
возвращает 0, если элементы равны * /

function maxDiff ($arr, $n)

{

    // Инициализируем diff, текущую сумму

    // и максимальная сумма

    $diff = $arr[1] - $arr[0];

    $curr_sum = $diff;

    $max_sum = $curr_sum;

  

    for($i = 1; $i < $n - 1; $i++)

    {

        // Рассчитать текущую разницу

        $diff = $arr[$i + 1] - $arr[$i];

  

        // Расчет текущей суммы

        if ($curr_sum > 0)

            $curr_sum += $diff;

        else

            $curr_sum = $diff;

  

        // Обновить максимальную сумму, если необходимо

        if ($curr_sum > $max_sum)

        $max_sum = $curr_sum;

    }

  

    return $max_sum;

}

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

$arr = array(80, 2, 6, 3, 100);

$n = sizeof($arr);

  
// вызов функции

echo "Maximum difference is ",

            maxDiff($arr, $n);

  
// Этот код добавлен
// по Sach_code
?>

Выход:

Maximum difference is 98

Сложность времени: O (n)
Вспомогательное пространство: O (1)

Ниже приведен вариант этой проблемы:
Максимальная разница суммы элементов в двух строках матрицы

Пожалуйста, пишите комментарии, если вы обнаружите какую-либо ошибку в приведенных выше кодах / алгоритмах, или найдете другие способы решения той же проблемы.

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

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

0.00 (0%) 0 votes