Найдите максимальную сумму на основе данной двоичной строки

Дана двоичная строка str и массив положительных целых чисел profit[] . Задача состоит в том, чтобы найти максимально возможную сумму, если нам разрешено использовать только элементы, соответствующий индекс которых имеет «1» в двоичной строке, и любую подстроку «01» можно заменить на подстроку «10».

Примеры:

Input: str = “01110”, profit[] = {10, 5, 8, 9, 6}
Output: 27
Explanation: Initially, the profit is 5 + 8 + 9 = 22. After one operation, the string can be made “10110” which will give the sum as 10 + 8 + 9 = 27.

Input: str = “011011”, profit[] = {20, 10, 9, 30, 20, 9}
Output: 80

Подход: Это можно решить, используя следующую идею.

The problem can be solved using a greedy approach. We can set any ‘0’ bit if there is at least one ‘1’ after it in the string. Consider, there are X 1s in the string. So the optimal idea is to select top X elements from the array such that they all lie before the last ‘1’ of the binary string.

We can implement this idea using a max heap (priority queue).

Выполните шаги, указанные ниже, чтобы решить проблему:

• Инициализируйте приоритетную очередь (скажем, pq ), которая будет реализовывать максимальную кучу.
• Перебрать двоичную строку и для каждого индекса:
  • Введите соответствующее значение массива в приоритетную очередь.
  • Если символ в двоичной строке равен «1», извлеките самый верхний элемент и добавьте его к ответу.
• Верните ответ после завершения итерации.

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

Сложность времени: O(N * logN), где N — длина массива.
Вспомогательное пространство: O(N)

Статьи по Теме:

• Введение в массивы - учебные пособия по структурам данных и алгоритмам
• Введение в кучу - учебные пособия по структурам данных и алгоритмам
• k самых больших (или самых маленьких) элементов в массиве