Максимизируйте значение (A[i]-A[j])*A[k] для любой упорядоченной тройки индексов i, j и k

Дан массив A , состоящий из N положительных целых чисел. и для любой упорядоченной тройки ( i, j, k ), такой что i, j и k все различны и 0 ≤ i, j, k < N , значение этой тройки равно (A _i − A _j )⋅A _{k ,} задача состоит в том, чтобы найти максимальное значение среди всех различных упорядоченных троек.

Примечание. Две тройки (a, b, c) и (d, e, f) считаются различными, если выполняется хотя бы одно из условий, таких как a ≠ d или b ≠ e или c ≠ f. Например, (1, 2, 3) и (2, 3, 1) — две тройки с разным порядком.

Примеры:

Input: A[] =  {1, 1, 3}
Output: 2

Explanation: The desired triplet is (2, 1, 0), which yields the value of (A_i−A_j)⋅A_k = (3 − 1)⋅1 = 2.

Input: A[] =  {3, 4, 4, 1, 2}
Output: 12

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

Sort the array A in increasing order. Since we want to maximize the value of (A_i − A_j).A_k, and all elements in A are positive, it is best to maximise both (A_i − A_j) and A_k. There are two options:

• Select largest and smallest element in A as A_i and A_j, and choose second maximum element in A as A_k. The value is (A_N-1 − A₀).A_N−2
• Choose the maximum element as A_k and choose the second maximum element, and the minimum element as A_i and A_j, getting a triplet of value (A_N-2 − A₀).A_N-1

Since A_{N – 2} ≤ A_N-1, we can prove that  (A_N-1 − A₀).A_N−2 ≥ (A_N-2 − A₀).A_N-1. Hence, the maximum value we can obtain is  
(A_N-1 − A₀).A_N−2 

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

• Отсортируйте массив в порядке возрастания.
• Найдите разницу между максимальным и минимальным элементом отсортированного массива
• Затем умножьте разницу на второй максимальный элемент отсортированного массива, чтобы получить ответ.

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

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