Максимизируйте сумму GCD двух подмножеств данного массива

Дан массив arr[] натуральных чисел размера N , задача состоит в том, чтобы разделить массив на два непустых подмножества X и Y так, чтобы сумма их НОД оказалась максимально возможной

Примеры:

Input: N = 3, arr[] = {1, 2, 9}
Output: 10
Explanation:  We can divide the array as
X = (1, 2) with GCD = 1
Y = (9) with GCD = 9
Maximum sum comes as 10

Input: N = 4, arr[] = {7, 21, 27, 28}
Output: 34
Explanation: Possible dividings :
X=  7, 21, 28 with GCD = 7 and Y = 27 with GCD =27. Sum = 34
X = 7, 21, 27 with GCD = 1 and Y = 28 with GCD =28. Sum = 29
Use the first way for the maximum sum possible i.e., 34. 

Подход: Задача может быть решена на основе следующей идеи:

To get the maximum GCD sum, keep the highest one in one subset (say X) and the others in another (say Y). 
But it can give raise to a case where the second maximum unique element causes the GCD of Y = 1 but the maximum element when considered in Y and the second max in X then the GCD sum may be greater. (Happens when the maximum element when kept with elements of Y subset the GCD is greater than 1 but when 2nd largest was in Y it was 1). 
We don’t need to consider for 3rd largest because if both first and second largest are divisible by the GCD then there difference is greater than the GCD[say a] and 3rd largest + a < 1 + largest as largest > 3rd largest+a

• So for gaining max gcd sum we will take gcd of smallest n-2 unique elements.
• Find including which one gives the greater sum. 

Выполните следующие шаги, чтобы лучше понять:

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

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

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