Наибольшее число, имеющее как положительные, так и отрицательные значения, присутствующие в массиве

Учитывая массив arr[] , состоящий из N целых чисел, задача состоит в том, чтобы найти наибольшее число K ( > 0 ), такое, что оба значения K и -K присутствуют в данном массиве arr[] . Если такого числа не существует, выведите -1 .

Примеры:

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

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

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

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

Эффективный подход. Описанный выше подход можно оптимизировать с помощью сортировки и двух указателей. Выполните следующие шаги, чтобы решить эту проблему:

• Инициализируйте переменную, скажем, res как -1 , которая хранит максимальный полученный элемент.
• Отсортируйте данный массив arr[].
• Инициализируйте две переменные, скажем, l и r как 0 и (N – 1) и выполните следующие шаги:
  • Если значение (arr[l] + arr[r]) равно 0 , то вернуть абсолютное значение arr[l] и arr[r].
  • В противном случае, если значение (arr[l] + arr[r]) меньше 0 , то увеличить значение l на 1 .
  • В противном случае уменьшите значение r на 1 .
• После выполнения вышеуказанных шагов выведите в качестве результата значение res .

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

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

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

• Инициализируйте набор S , в котором хранятся элементы массива.
• Инициализируйте переменную, скажем, res как -1 , чтобы сохранить максимальный элемент при обходе массива.
• Переберите диапазон [0, N – 1], используя переменную i , и выполните следующие шаги:
  • Добавьте текущий элемент в набор S .
  • Если элемент присутствует, то обновите значение res до текущего элемента.
• После выполнения вышеуказанных шагов выведите в качестве результата значение res .

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

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