Максимизируйте количество уникальных элементов в массиве, изменив элементы на отрицательные

Дан массив arr , содержащий N целых чисел. задача состоит в том, чтобы найти максимальное количество уникальных элементов в массиве, если каждый элемент в массиве можно изменить на его отрицательное значение, т.е. X можно изменить на -X в массиве.

Пример:

Input: arr[] = {-1, 3, 2, 3, 2}
Output: 5
Explanation: Change one 2 to -2 and another 3 to -3 to get the arr[]={-1, 3, 2, -3, -2}, having 5 unique values.

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

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

• Пройдите массив от i=0 до i<N и для каждого элемента arr[i] :
  • Проверьте, присутствует ли в наборе abs(arr[i]) или нет.
  • Если его нет, то вставьте его в набор.
  • В противном случае вставьте исходное значение в набор.
• Поскольку набор содержит только исходные значения, ответом будет размер набора.

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

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