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

Опубликовано: 25 Февраля, 2023

Дан массив A[] длины N, выбираем любые два элемента x и y из массива, задача состоит в том, чтобы найти максимальное значение выражения (x * y + x – y).

Примеры:

Input: A[] = {5, 2, 3} 
Output: 17
Explanation: There are six possible pairs:
For pairs {2, 3} and {3, 2}, answer = 2 ∗ 3 + max(2−3, 3−2) = 7
For pairs {3, 5} and {5, 3} answer = 5 ∗ 3 + max(3−5, 5−3) = 17 and 
For pairs {2, 5} and {5, 2}, answer = 2 ∗ 5 + max(2−5, 5−2) = 13.
So final answer is maximum of {7, 17, 13} = 17.

Input: A[] = {3, 7, 4, 9} 
Output: 65

Подход: Задача может быть решена на основе следующего наблюдения:

Rewriting x∗y + x−y = (x−1)∗(y+1) + 1
To maximize the value of the expression we have to maximize the value of x*y.
So there can be two choices:

  • If the minimum and second minimum both are negative, their product will be positive and that can be a valid answer.
  • If the maximum and second maximum both are positive, their product will be positive and that can be the required pair.

So find the minimum and second minimum and maximum and second maximum and check for the above cases. The maximum will be the answer.

Выполните следующие шаги, чтобы реализовать вышеуказанную идею:

  • Сначала отсортируйте массив.
  • Выберите минимум, второй минимум, максимум и второй максимум элемента массива.
  • После этого найдите значение выражения для x = минимум и y = второй минимум и x = максимум и y = второй максимум и сохраните их в sum1 и sum2 соответственно.
  • Найдите максимум между sum1 и sum2 и выведите это значение.

Ниже приведена реализация описанного выше подхода.

Временная сложность: O (N * log (N))
Вспомогательное пространство: O(1)

РЕКОМЕНДУЕМЫЕ СТАТЬИ