Рубрики

Для данного массива arr [] найдите максимум j — i такой, что arr [j]> arr [i]

Для данного массива arr [] найдите максимум j — i такой, что arr [j]> arr [i].

Примеры :

  Input: {34, 8, 10, 3, 2, 80, 30, 33, 1}
  Output: 6  (j = 7, i = 1)

  Input: {9, 2, 3, 4, 5, 6, 7, 8, 18, 0}
  Output: 8 ( j = 8, i = 0)

  Input:  {1, 2, 3, 4, 5, 6}
  Output: 5  (j = 5, i = 0)

  Input:  {6, 5, 4, 3, 2, 1}
  Output: -1 

Метод 1 (простой, но неэффективный)
Запустите две петли. Во внешнем цикле выберите элементы один за другим слева. Во внутреннем цикле сравните выбранный элемент с элементами, начиная с правой стороны. Остановите внутренний цикл, когда увидите элемент больше выбранного элемента, и продолжайте обновлять максимальное значение ji.

C ++

#include <bits/stdc++.h>

  

using namespace std;

/ * Для данного массива arr [] возвращает максимальное значение j - i, такое что

    arr [j]> arr [i] * /

int maxIndexDiff(int arr[], int n)

{

    int maxDiff = -1;

    int i, j;

  

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

    {

        for (j = n-1; j > i; --j)

        {

            if(arr[j] > arr[i] && maxDiff < (j - i))

                maxDiff = j - i;

        }

    }

  

    return maxDiff;

}

  

int main()

{

    int arr[] = {9, 2, 3, 4, 5, 6, 7, 8, 18, 0};

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

    int maxDiff = maxIndexDiff(arr, n);

    cout<< "\n" << maxDiff;

    return 0;

}

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

С

#include <stdio.h>
/ * Для данного массива arr [] возвращает максимальное значение j - i, такое что

    arr [j]> arr [i] * /

int maxIndexDiff(int arr[], int n)

{

    int maxDiff = -1;

    int i, j;

  

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

    {

        for (j = n-1; j > i; --j)

        {

            if(arr[j] > arr[i] && maxDiff < (j - i))

                maxDiff = j - i;

        }

    }

  

    return maxDiff;

}

  

int main()

{

    int arr[] = {9, 2, 3, 4, 5, 6, 7, 8, 18, 0};

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

    int maxDiff = maxIndexDiff(arr, n);

    printf("\n %d", maxDiff);

    getchar();

    return 0;

}

Джава

class FindMaximum 

{

    / * Для данного массива arr [] возвращает максимальное значение ji, такое что

       arr [j]> arr [i] * /

    int maxIndexDiff(int arr[], int n) 

    {

        int maxDiff = -1;

        int i, j;

  

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

        {

            for (j = n - 1; j > i; --j) 

            {

                if (arr[j] > arr[i] && maxDiff < (j - i))

                    maxDiff = j - i;

            }

        }

  

        return maxDiff;

    }

  

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

    public static void main(String[] args) 

    {

        FindMaximum max = new FindMaximum();

        int arr[] = {9, 2, 3, 4, 5, 6, 7, 8, 18, 0};

        int n = arr.length;

        int maxDiff = max.maxIndexDiff(arr, n);

        System.out.println(maxDiff);

    }

}

python3

# Python3 программа для поиска максимума
# j - я такой, что arr [j]> arr [i]

   
# Для заданного массива arr [] возвращает
# максимальный j - я такой, что
# arr [j]> arr [i]

def maxIndexDiff(arr, n):

    maxDiff = -1

    for i in range(0, n):

        j = n - 1

        while(j > i):

            if arr[j] > arr[i] and maxDiff < (j - i):

                maxDiff = j - i;

            j -= 1

      

    return maxDiff

  
# код водителя

arr = [9, 2, 3, 4, 5, 6, 7, 8, 18, 0]

n = len(arr)

maxDiff = maxIndexDiff(arr, n)

print(maxDiff)

  
# Эта статья предоставлена Смитой Динеш Семвал

C #

// C # программа для поиска максимума
// j - i такой, что arr [j]> arr [i]

using System;

class GFG

{

    // Для данного массива arr [], возвращает

    // максимальное значение ji такое, что arr [j]> arr [i]

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

    {

        int maxDiff = -1;

        int i, j;

  

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

        {

            for (j = n - 1; j > i; --j) 

            {

                if (arr[j] > arr[i] && maxDiff < (j - i))

                    maxDiff = j - i;

            }

        }

  

        return maxDiff;

    }

  

    // Драйвер программы

    public static void Main() 

    {

          

        int []arr = {9, 2, 3, 4, 5, 6, 7, 8, 18, 0};

        int n = arr.Length;

        int maxDiff = maxIndexDiff(arr, n);

        Console.Write(maxDiff);

    }

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

PHP

<?php
// PHP программа для поиска максимума
// j - i такой, что arr [j]> arr [i]

  
// Для данного массива arr [], возвращает
// максимальное j - я такое, что
// arr [j]> arr [i]

function maxIndexDiff($arr, $n)

{

    $maxDiff = -1;

      

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

    {

        for ($j = $n - 1; $j > $i; --$j)

        {

            if($arr[$j] > $arr[$i] && 

               $maxDiff < ($j - $i))

                $maxDiff = $j - $i;

        }

    }

  

    return $maxDiff;

}

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

$arr = array(9, 2, 3, 4, 5, 

             6, 7, 8, 18, 0);

$n = count($arr);

$maxDiff = maxIndexDiff($arr, $n);

echo $maxDiff ;

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

Выход:

8

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

Метод 2 O (nLgn)
Используйте хеширование и сортировку, чтобы решить эту проблему с меньшей степенью сложности после особой заботы о дубликатах.
Подходить :

  1. Обойдите массив и сохраните индекс каждого элемента в списке (для обработки дубликатов).
  2. Сортировать массив.
  3. Теперь пройдитесь по массиву и отследите максимальную разницу между i и j.
  4. Для j рассмотрим последний индекс из списка возможных индексов элемента, а для i рассмотрим первый индекс из списка. (Так как индекс был добавлен в порядке возрастания).
  5. Продолжайте обновлять максимальную разницу до конца массива.

python3

# Python3 реализация вышеуказанного подхода

n = 9

a = [34, 8, 10, 3, 2, 80, 30, 33, 1]

  
# Сохранить индекс элемента.

index = dict() 

for i in range(n):

    if a[i] in index:

  

        #append к списку (для дубликатов)

        index[a[i]].append(i)  

    else:

  

        # если первое вхождение

        index[a[i]] = [i]   

  
# сортировать входной массив
a.sort()     

maxDiff = 0

  
# Временная переменная для отслеживания минимального я

temp = n     

for i in range(n):

    if temp > index[a[i]][0]:

        temp = index[a[i]][0]

    maxDiff = max(maxDiff, index[a[i]][-1]-temp)

  

print(maxDiff)

Выход:

6

Временная сложность: O (N * log (N))
Метод 3 (Эффективный)
Чтобы решить эту проблему, нам нужно получить два оптимальных индекса arr []: левый индекс i и правый индекс j. Для элемента arr [i] нам не нужно рассматривать arr [i] для левого индекса, если в левой части arr [i] есть элемент меньше, чем arr [i]. Аналогично, если в правой части arr [j] есть больший элемент, нам не нужно рассматривать этот j для правильного индекса. Таким образом, мы строим два вспомогательных массива LMin [] и RMax [] так, чтобы LMin [i] содержал наименьший элемент в левой части arr [i], включая arr [i], а RMax [j] содержал наибольший элемент в правой части arr [j], включая arr [j]. После построения этих двух вспомогательных массивов мы пересекаем оба этих массива слева направо. Обходя LMin [] и RMa [], если мы видим, что LMin [i] больше чем RMax [j], то мы должны двигаться вперед в LMin [] (или сделать i ++), потому что все элементы слева от LMin [i] больше или равно LMin [i]. В противном случае мы должны двигаться вперед в RMax [j], чтобы найти большее значение j — i.

Спасибо celicom за предложенный алгоритм для этого метода.

C ++

#include <bits/stdc++.h>

using namespace std; 

  
/ * Для данного массива arr [],

   возвращает максимум j - я такой, что

   arr [j]> arr [i] * /

int maxIndexDiff(int arr[], int n) 

    int maxDiff; 

    int i, j; 

  

    int *LMin = new int[(sizeof(int) * n)]; 

    int *RMax = new int[(sizeof(int) * n)];

  

    / * Построить LMin [] так, чтобы

    LMin [i] хранит минимальное значение

    из (arr [0], arr [1], ... arr [i]) * /

    LMin[0] = arr[0]; 

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

        LMin[i] = min(arr[i], LMin[i - 1]); 

  

    / * Построить RMax [] так, чтобы

    RMax [j] хранит максимальное значение из

    (arr [j], arr [j + 1], ..arr [n-1]) * /

    RMax[n - 1] = arr[n - 1]; 

    for (j = n - 2; j >= 0; --j) 

        RMax[j] = max(arr[j], RMax[j + 1]); 

   

    / * Обходить оба массива слева направо

    найти оптимальный j - i. Этот процесс похож на

    merge () из MergeSort * /

    i = 0, j = 0, maxDiff = -1; 

    while (j < n && i < n) 

    

        if (LMin[i] < RMax[j]) 

        

            maxDiff = max(maxDiff, j - i); 

            j = j + 1; 

        

        else

            i = i + 1; 

    

  

    return maxDiff; 

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

int main() 

    int arr[] = {9, 2, 3, 4, 5, 

                 6, 7, 8, 18, 0}; 

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

    int maxDiff = maxIndexDiff(arr, n); 

    cout << maxDiff; 

    return 0; 

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

С

#include <stdio.h>

  
/ * Утилиты, чтобы получить максимум и минимум из двух целых чисел * /

int max(int x, int y)

{

    return x > y? x : y;

}

  

int min(int x, int y)

{

    return x < y? x : y;

}

  
/ * Для данного массива arr [] возвращает максимальное значение j - i, такое что

    arr [j]> arr [i] * /

int maxIndexDiff(int arr[], int n)

{

    int maxDiff;

    int i, j;

  

    int *LMin = (int *)malloc(sizeof(int)*n);

    int *RMax = (int *)malloc(sizeof(int)*n);

  

   / * Создайте LMin [] так, чтобы LMin [i] сохранял минимальное значение

       из (arr [0], arr [1], ... arr [i]) * /

    LMin[0] = arr[0];

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

        LMin[i] = min(arr[i], LMin[i-1]);

  

    / * Создайте RMax [] так, чтобы RMax [j] сохранял максимальное значение

       из (arr [j], arr [j + 1], ..arr [n-1]) * /

    RMax[n-1] = arr[n-1];

    for (j = n-2; j >= 0; --j)

        RMax[j] = max(arr[j], RMax[j+1]);

  

    / * Обходите оба массива слева направо, чтобы найти оптимальный j - i

        Этот процесс похож на merge () из MergeSort * /

    i = 0, j = 0, maxDiff = -1;

    while (j < n && i < n)

    {

        if (LMin[i] < RMax[j])

        {

            maxDiff = max(maxDiff, j-i);

            j = j + 1;

        }

        else

            i = i+1;

    }

  

    return maxDiff;

}

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

int main()

{

    int arr[] = {9, 2, 3, 4, 5, 6, 7, 8, 18, 0};

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

    int maxDiff = maxIndexDiff(arr, n);

    printf("\n %d", maxDiff);

    getchar();

    return 0;

}

Джава

class FindMaximum

{

    / * Утилиты, чтобы получить максимум и минимум из двух целых чисел * /

    int max(int x, int y) 

    {

        return x > y ? x : y;

    }

  

    int min(int x, int y) 

    {

        return x < y ? x : y;

    }

  

    / * Для данного массива arr [] возвращает максимальное значение ji, такое что

       arr [j]> arr [i] * /

    int maxIndexDiff(int arr[], int n) 

    {

        int maxDiff;

        int i, j;

  

        int RMax[] = new int[n];

        int LMin[] = new int[n];

  

        / * Создайте LMin [] так, чтобы LMin [i] сохранял минимальное значение

           из (arr [0], arr [1], ... arr [i]) * /

        LMin[0] = arr[0];

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

            LMin[i] = min(arr[i], LMin[i - 1]);

  

        / * Создайте RMax [] так, чтобы RMax [j] сохранял максимальное значение

           из (arr [j], arr [j + 1], ..arr [n-1]) * /

        RMax[n - 1] = arr[n - 1];

        for (j = n - 2; j >= 0; --j)

            RMax[j] = max(arr[j], RMax[j + 1]);

  

        / * Обходите оба массива слева направо, чтобы найти оптимальный j - i

           Этот процесс похож на merge () из MergeSort * /

        i = 0; j = 0; maxDiff = -1;

        while (j < n && i < n) 

        {

            if (LMin[i] < RMax[j]) 

            {

                maxDiff = max(maxDiff, j - i);

                j = j + 1;

            

            else 

                i = i + 1;

        }

  

        return maxDiff;

    }

  

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

    public static void main(String[] args) 

    {

        FindMaximum max = new FindMaximum();

        int arr[] = {9, 2, 3, 4, 5, 6, 7, 8, 18, 0};

        int n = arr.length;

        int maxDiff = max.maxIndexDiff(arr, n);

        System.out.println(maxDiff);

    }

}

python3

# Сервисные функции, чтобы получить максимум
# и минимум двух целых

def max(a, b):

    if(a > b):

        return a

    else:

        return b

  

def min(a,b):

    if(a < b):

        return a

    else:

        return b

  
# Для данного массива arr [],
# возвращает максимум j - i
# такой, что arr [j]> arr [i]

def maxIndexDiff(arr, n):

    maxDiff = 0;

    LMin = [0] * n

    RMax = [0] * n

  

    # Построить LMin [] так, чтобы

    # LMin [i] хранит минимум

    # значение из (arr [0], arr [1],

    # ... обр [я])

    LMin[0] = arr[0]

    for i in range(1, n):

        LMin[i] = min(arr[i], LMin[i - 1])

  

    # Построить RMax [] так, чтобы

    # RMax [j] хранит максимум

    # значение из (arr [j], arr [j + 1],

    # ..arr [n-1])

    RMax[n - 1] = arr[n - 1]

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

        RMax[j] = max(arr[j], RMax[j + 1]);

  

    # Обходите оба массива слева

    # вправо, чтобы найти оптимальное J - я

    # Этот процесс похож на

    # merge () из MergeSort

    i, j = 0, 0

    maxDiff = -1

    while (j < n and i < n):

        if (LMin[i] < RMax[j]):

            maxDiff = max(maxDiff, j - i)

            j = j + 1

        else:

            i = i+1

  

    return maxDiff

  
Код водителя

if(__name__ == '__main__'):

    arr = [9, 2, 3, 4, 5

           6, 7, 8, 18, 0]

    n = len(arr)

    maxDiff = maxIndexDiff(arr, n)

    print (maxDiff)

  
# Этот код добавлен
# Гаутам Каракоти

C #

// C # программа для поиска максимума
// j - i такой, что arr [j]> arr [i]

using System;

  

class GFG

{

    // Функции утилиты для получения максимума

    // и минимум двух целых

    static int max(int x, int y) 

    {

        return x > y ? x : y;

    }

  

    static int min(int x, int y) 

    {

        return x < y ? x : y;

    }

  

    // Для данного массива arr [], возвращает

    // максимальное значение ji такое, чтоarr [j]> arr [i]

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

    {

        int maxDiff;

        int i, j;

  

        int []RMax = new int[n];

        int []LMin = new int[n];

  

        // Создаем LMin [] так, чтобы LMin [i]

        // сохраняет минимальное значение

        // from (arr [0], arr [1], ... arr [i])

        LMin[0] = arr[0];

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

            LMin[i] = min(arr[i], LMin[i - 1]);

  

        // Построить RMax [] так, чтобы

        // RMax [j] сохраняет максимальное значение

        // from (arr [j], arr [j + 1], ..arr [n-1])

        RMax[n - 1] = arr[n - 1];

        for (j = n - 2; j >= 0; --j)

            RMax[j] = max(arr[j], RMax[j + 1]);

  

        // Обходим оба массива слева

        // вправо, чтобы найти оптимальное J - я

        // Этот процесс похож на merge ()

        // of MergeSort

        i = 0; j = 0; maxDiff = -1;

        while (j < n && i < n) 

        {

            if (LMin[i] < RMax[j]) 

            {

                maxDiff = max(maxDiff, j - i);

                j = j + 1;

            

            else

                i = i + 1;

        }

  

        return maxDiff;

    }

  

    // Драйвер программы

    public static void Main() 

    {

          

        int []arr = {9, 2, 3, 4, 5, 6, 7, 8, 18, 0};

        int n = arr.Length;

        int maxDiff = maxIndexDiff(arr, n);

        Console.Write(maxDiff);

    }

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

PHP

<?php 
// PHP программа для поиска максимума
// j - i такой, что arr [j]> arr [i]

  
// Для данного массива arr [],
// возвращает максимум j - i
// такой, что arr [j]> arr [i]

function maxIndexDiff($arr, $n)

{

    $maxDiff = 0;

    $LMin = array_fill(0, $n, NULL);

    $RMax = array_fill(0, $n, NULL);

  

    // Создаем LMin [] так, чтобы

    // LMin [i] хранит минимум

    // значение из (arr [0], arr [1],

    // ... arr [i])

    $LMin[0] = $arr[0];

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

        $LMin[$i] = min($arr[$i], 

                        $LMin[$i - 1]);

  

    // Построить RMax [] так, чтобы

    // RMax [j] сохраняет максимум

    // значение из (arr [j], arr [j + 1],

    // ..arr [n-1])

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

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

        $RMax[$j] = max($arr[$j], 

                        $RMax[$j + 1]);

  

    // Обходим оба массива слева

    // вправо, чтобы найти оптимальное J - я

    // Этот процесс похож на

    // merge () из MergeSort

    $i = 0;

    $j = 0;

    $maxDiff = -1;

    while ($j < $n && $i < $n)

        if ($LMin[$i] < $RMax[$j])

        {

            $maxDiff = max($maxDiff, $j - $i);

            $j = $j + 1;

        }

        else

            $i = $i + 1;

  

    return $maxDiff;

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

$arr = array(9, 2, 3, 4, 5, 

             6, 7, 8, 18, 0);

$n = sizeof($arr);

$maxDiff = maxIndexDiff($arr, $n);

echo $maxDiff;

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

Выход:

8

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

Спросил в: Amazon , Google , VMWare

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

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

Для данного массива arr [] найдите максимум j — i такой, что arr [j]> arr [i]

0.00 (0%) 0 votes