Максимальная сумма пары несмежных элементов в массиве

Учитывая массив arr[] различных целых чисел, найдите пару с максимальной суммой, такую, что оба элемента пары не являются соседними в массиве

Примеры:

Input: arr[] = {7, 3, 4, 1, 8, 9}
Output: 9 7
Explanation: Pair with maximum sum is (8, 9). 
But since both elements are adjacent, it is not a valid pair. 
Therefore, the pair with maximum sum is (9, 7) with sum 16. 

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

Input: arr[] = {4, 3, 7, 9, 8, 1}
Output: 7 8
Explanation: Sum of both the pairs {7, 9} and {9, 8} are greater.
But they are adjacent pairs. Hence this is the valid answer.

Подход : Идея состоит в том, чтобы вычислить индексы трех самых больших элементов в массиве. После вычисления индексов проверьте пару с максимальной суммой , а также проверьте, являются ли они соседними или нет. Всегда можно получить по крайней мере одну пару с двумя несмежными элементами, поскольку были вычислены три самых больших элемента.

Ниже приведена реализация вышеуказанного подхода:

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