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

31.12.2019Массивы

Дан массив из 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);

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

Выход :

Как это работает?
Важно показать, что мы не пропускаем ни одной потенциальной пары в вышеупомянутом линейном алгоритме, т.е. нам нужно показать, что выполнение 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