Максимизируйте значение (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 (Ai−Aj)⋅Ak = (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 (Ai − Aj).Ak, and all elements in A are positive, it is best to maximise both (Ai − Aj) and Ak. There are two options:
- Select largest and smallest element in A as Ai and Aj, and choose second maximum element in A as Ak. The value is (AN-1 − A0).AN−2
- Choose the maximum element as Ak and choose the second maximum element, and the minimum element as Ai and Aj, getting a triplet of value (AN-2 − A0).AN-1
Since AN – 2 ≤ AN-1, we can prove that (AN-1 − A0).AN−2 ≥ (AN-2 − A0).AN-1. Hence, the maximum value we can obtain is
(AN-1 − A0).AN−2
Выполните следующие шаги, чтобы решить проблему:
- Отсортируйте массив в порядке возрастания.
- Найдите разницу между максимальным и минимальным элементом отсортированного массива
- Затем умножьте разницу на второй максимальный элемент отсортированного массива, чтобы получить ответ.
Ниже приведена реализация описанного выше подхода.
Временная сложность: O(N * log(N))
Вспомогательное пространство: O(1)