Максимально возможная разность суммы двух подмножеств массива | Набор 2
Дан массив arr[ ] , состоящий из N целых чисел. Задача состоит в том, чтобы найти максимальную разность между суммой двух подмножеств, полученной путем разбиения массива на любые два непустых подмножества.
Примечание . Подмножества не могут содержать каких-либо общих элементов. Подмножество может содержать повторяющиеся элементы.
Примеры:
Input: arr[] = {1, 3, 2, 4, 5}
Output: 13
Explanation: The partitions {3, 2, 4, 5} and {1} maximizes the difference between the subsets.Input: arr[] = {1, -5, 3, 2, -7}
Output: 18
Explanation: The partitions {1, 3, 2} and {-5, -7} maximizes the difference between the subsets.
Подход: Эту проблему можно решить с помощью жадного подхода. В этой задаче оба подмножества A и B должны быть непустыми. Таким образом, мы должны поместить хотя бы один элемент в оба из них. Мы пытаемся сделать сумму элементов в подмножестве A как можно больше, а сумму элементов в подмножестве B как можно меньше. Наконец, мы печатаем сумму (A) – сумму (B).
Следуйте инструкциям ниже, чтобы решить проблему:
- Когда arr[ ] содержит как неотрицательные, так и отрицательные числа, поместите все неотрицательные числа в подмножество A и отрицательные числа в подмножество B и выведите sum(A) – sum(B) .
- Когда все числа положительны, поместите все числа в подмножество A, кроме наименьшего положительного числа, поместите его в подмножество B и выведите sum(A) – sum(B) .
- Когда все числа отрицательные, поместите все числа в подмножество B, кроме самого большого отрицательного, поместите его в подмножество A и выведите сумму (A) – сумму (B).
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(NlogN)
Вспомогательное пространство: O(N)