Рубрики

Найти максимальное значение abs (i — j) * min (arr [i], arr [j]) в массиве arr []

Дан массив из n различных элементов. Найти максимальное произведение минимума двух чисел в массиве и абсолютную разницу их позиций, т. Е. Найти максимальное значение abs (i — j) * min (arr [i], arr [j]), где i и j меняются от 0 до n-1.
Примеры :

Input : arr[] = {3, 2, 1, 4}
Output: 9
// arr[0] = 3 and arr[3] = 4 minimum of them is 3 and 
// absolute difference between their position is 
// abs(0-3) = 3. So product is 3*3 = 9

Input : arr[] = {8, 1, 9, 4}
Output: 16
// arr[0] = 8 and arr[2] = 9 minimum of them is 8 and 
// absolute difference between their position is 
// abs(0-2) = 2. So product is 8*2 = 16 

Простое решение этой проблемы — взять каждый элемент один за другим и сравнить этот элемент с элементами справа от него. Затем рассчитайте произведение минимума из них и абсолютной разницы между их показателями и максимизируйте результат. Временная сложность для этого подхода O (n ^ 2).

Эффективное решение для решения задачи в линейной сложности времени. Мы берем два итератора Left = 0 и Right = n-1 , сравниваем элементы arr [Left] и arr [right].

left = 0, right = n-1
maxProduct = -INF
While (left < right)
    If arr[Left] < arr[right] 
        currProduct = arr[Left]*(right-Left) 
        Left++ . 
    If arr[right] < arr[Left] 
        currProduct = arr[Right]*(Right-Left) 
        Right-- . 
  
    maxProduct = max(maxProduct, currProduct)

Ниже приведена реализация вышеуказанной идеи.

C ++

// C ++ реализация кода
#include<bits/stdc++.h>

using namespace std;

  
// Функция для расчета максимального значения
// abs (i - j) * min (arr [i], arr [j]) в arr []

int Maximum_Product(int arr[], int n)

{

    int maxProduct = INT_MIN; // Инициализировать результат

    int currProduct; // произведение текущей пары

  

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

    int Left = 0, right = n-1;

    while (Left < right)

    {

        if (arr[Left] < arr[right])

        {

            currProduct = arr[Left]*(right-Left);

            Left++;

        }

        else // arr [right] меньше

        {

            currProduct = arr[right]*(right-Left);

            right--;

        }

  

        // максимизация продукта

        maxProduct = max(maxProduct, currProduct)

    }

  

    return maxProduct;

}

  
// Драйвер программы для проверки кейса

int main()

{

    int arr[] = {8, 1, 9, 4};

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

    cout << Maximum_Product(arr,n);

    return 0;

}

Джава

// Java реализация кода

import java.util.*;

  

class GFG {

      

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

    // abs (i - j) * min (arr [i], arr [j]) в arr []

    static int Maximum_Product(int arr[], int n) {

          

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

    int maxProduct = Integer.MIN_VALUE; 

      

    // произведение текущей пары

    int currProduct;            

  

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

    int Left = 0, right = n - 1;

    while (Left < right) {

    if (arr[Left] < arr[right]) {

        currProduct = arr[Left] * (right - Left);

        Left++;

    

      

    // arr [right] меньше

    else 

    {

        currProduct = arr[right] * (right - Left);

        right--;

    }

  

    // максимизация продукта

    maxProduct = Math.max(maxProduct, currProduct);

    }

  

    return maxProduct;

}

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

public static void main(String[] args) 

{

    int arr[] = {8, 1, 9, 4};

    int n = arr.length;

    System.out.print(Maximum_Product(arr, n));

}
}

  
// Этот код предоставлен Anant Agarwal.

python3

# Python реализация кода
# Функция для расчета
# максимальное значение
# abs (i - j) * min (обр. [i],
# arr [j]) в arr []

def Maximum_Product(arr,n):

      

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

    maxProduct = -2147483648 

  

    # произведение текущей пары

    currProduct=0 

   

    # цикл, пока они не встретятся друг с другом

    Left = 0

    right = n-1

    while (Left < right):

      

        if (arr[Left] < arr[right]):

          

            currProduct = arr[Left]*(right-Left)

            Left+=1

          

        else

  

            # arr [right] меньше

            currProduct = arr[right]*(right-Left)

            right-=1

          

   

        # максимизация продукта

        maxProduct = max(maxProduct, currProduct)

      

   

    return maxProduct

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

  

arr = [8, 1, 9, 4]

n = len(arr)

  

print(Maximum_Product(arr,n))

  
# Этот код добавлен
# Анант Агарвал.

C #

// C # реализация кода

using System;

  

class GFG {

      
// Функция для расчета максимума
// значение abs (i - j) * min (arr [i],
// arr [j]) в arr []

static int Maximum_Product(int []arr,

                           int n)

{

          

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

    int maxProduct = int.MinValue; 

      

    // произведение текущей пары

    int currProduct;         

  

    // цикл, пока они не встретятся

    // друг с другом

    int Left = 0, right = n - 1;

    while (Left < right) {

    if (arr[Left] < arr[right])

    {

        currProduct = arr[Left] * 

                      (right - Left);

        Left++;

    

      

    // arr [right] меньше

    else

    {

        currProduct = arr[right] *

                      (right - Left);

        right--;

    }

  

    // максимизация продукта

    maxProduct = Math.Max(maxProduct, 

                          currProduct);

    }

  

    return maxProduct;

}

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

public static void Main() 

{

    int []arr = {8, 1, 9, 4};

    int n = arr.Length;

    Console.Write(Maximum_Product(arr, n));

}
}

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

PHP

<?php
// PHP реализация кода

  
// Функция для расчета
// максимальное значение
// abs (i - j) * min (arr [i],
// arr [j]) в arr []

function Maximum_Product($arr, $n)

{

    $INT_MIN = 0;

      

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

    $maxProduct = $INT_MIN

      

    // произведение текущей пары

    $currProduct

  

    // цикл, пока они не встретятся

    // друг с другом

    $Left = 0; $right = $n - 1;

    while ($Left < $right)

    {

        if ($arr[$Left] < $arr[$right])

        {

            $currProduct = $arr[$Left] * 

                          ($right - $Left);

            $Left++;

        }

          

        // arr [right] меньше

        else 

        {

            $currProduct = $arr[$right] * 

                          ($right - $Left);

            $right--;

        }

  

        // максимизация продукта

        $maxProduct = max($maxProduct

                          $currProduct);

    }

  

    return $maxProduct;

}

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

$arr = array(8, 1, 9, 4);

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

echo Maximum_Product($arr, $n);

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


Выход :

 16

Как это работает?
Важно показать, что мы не пропускаем ни одной потенциальной пары в вышеупомянутом линейном алгоритме, т.е. нам нужно показать, что выполнение left ++ или right — не приводит к случаю, когда мы получили бы более высокое значение maxProduct.

Обратите внимание, что мы всегда умножаем на (справа — слева).

1) Если arr [left] <arr [right], то меньшие значения right для текущего left бесполезны, так как не могут дать более высокое значение maxProduct (потому что мы умножаемся на arr [left] с (right — left)). Что делать, если arr [left] больше, чем любой из элементов на левой стороне. В этом случае лучшая пара для этого элемента должна быть найдена с текущим правом. Поэтому мы можем безопасно увеличить левое, не пропуская лучшую пару с текущим левым.

2) Аналогичные аргументы применимы, когда arr [right] <arr [left].

Эта статья предоставлена Шашанком Мишрой (Гуллу) . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

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

Найти максимальное значение abs (i — j) * min (arr [i], arr [j]) в массиве arr []

0.00 (0%) 0 votes