Программа Php для количества пар с максимальной суммой

Учитывая массив arr[], подсчитайте количество пар arr[i], arr[j] таких, что arr[i] + arr[j] является максимальным и i < j.

Example :
Input  : arr[] = {1, 1, 1, 2, 2, 2}
Output : 3
Explanation: The maximum possible pair 
sum where i
Метод 1 (Наивный)
 Пройдите цикл i от 0 до n, т.е. длину массива, и другой цикл j от i+1 до n, чтобы найти все возможные пары с i 
Выход :
3
Временная сложность: O(n^2)
Способ 2 (эффективный)
 Если присмотреться, то можно заметить следующие факты.
Максимальный элемент всегда является частью решения
 Если максимальный элемент встречается более одного раза, результатом будет maxCount * (maxCount - 1)/2. В основном нам нужно выбрать 2 элемента из maxCount ( maxCount C 2 ).
 Если максимальный элемент появляется один раз, то результат равен количеству второго максимального элемента. Мы можем образовать пару с каждым вторым max и max
Выход :
3
Временная сложность: O(n)
Пожалуйста, обратитесь к полной статье о количестве пар с максимальной суммой для получения более подробной информации!