Максимизируйте сумму выбранных чисел из массива, чтобы очистить его | Набор 2

Учитывая массив arr[] из N целых чисел, задача состоит в том, чтобы максимизировать сумму выбранных чисел по всем операциям так, чтобы в каждой операции выбрать число A _i , удалить одно его вхождение и удалить все вхождения A _i – 1 и A _i + 1 (если они существуют) в массиве до тех пор, пока массив не станет пустым.

Примеры:

Input: arr[] = {3, 4, 2}
Output: 6
Explanation: In 1st operation, select 4 and delete it. Therefore, all occurrences of 3 and 5 are deleted from arr[]. The array after the operation is arr[] = {2}. In 2nd operation select 2. Hence, the sum of all selected numbers = 4+2 = 6 which is the maximum possible.

Input: arr[] = {2, 2, 3, 3, 3, 4}
Output: 9
Explanation: In 1st operation, select 3 and delete it. Therefore, all occurrences of 2 and 4 are deleted from arr[]. The array after the operation is arr[] = {3, 3}. In 2nd and 3rd operation select 3. Hence, the sum of all selected numbers = 3+3+3 = 9, which is the maximum possible.

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

Временная сложность: O(M + F), где M — максимальный элемент массива, а F — максимальная частота элемента массива.
Вспомогательное пространство: O(M), где M — максимальный элемент массива.

Подход динамического программирования. Вышеупомянутый подход также можно оптимизировать и решить с помощью динамического программирования. Можно заметить, что если число A _i из массива arr[] выбрано, оно внесет A _i * freq[A _i ] в окончательную сумму. Используя это наблюдение, выполните следующие шаги, чтобы решить данную проблему:

• Создайте массив freq[] , в котором хранится частота каждого элемента массива arr[] .
• Создайте одномерный массив dp[] , где dp[i] представляет максимально возможную сумму выбранных значений, лежащих в диапазоне [1, i] в данном массиве.
• Для каждого значения i возможны два следующих случая:
  • Случай 1, где выбрано i . В этом случае значение dp[i] = freq[i] * i + dp[i-2] .
  • Случай 2, где выбрано i – 1 . В этом случае значение dp[i] = dp[i-1] .
• Следовательно, отношение DP вышеупомянутой проблемы:

dp[i] = max( dp[i – 1], (freq[i] * i)+ dp[i – 2]) for all values of i in range [0, MAX] where MAX is the maximum integer in arr[]

• Значение, хранящееся в dp[MAX] , является требуемым ответом.

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

Временная сложность: O(M + F), где M — максимальный элемент массива .
Вспомогательное пространство: O(M), где M — максимальный элемент массива .