Максимальная сумма сегментов среди всех сегментов, сформированных в массиве после Q запросов

Имея два массива arr[] (индексация на основе 1) и query[] , состоящие из N целых чисел, и query[] содержит перестановку первых N натуральных чисел, задача состоит в том, чтобы выполнить запрос к массиву и найти максимальную сумму сегменты среди всех сегментов сформированы таким образом, что в каждом запросе query [i] элемент массива по индексу query[ i] удаляется, и этот сегмент делится на 2 сегмента.

Примеры:

Input: arr[] = {1, 3, 2, 5}, queries[] = {3, 4, 1, 2}
Output: 5 4 3 0
Explanation:
Following are the queries performed:

• Query 1: Remove the element at index 3 break the current array into {1, 3}, {5}. The maximum sum among all segments is 5.
• Query 2: Remove the element at index 4 break the current array into {1, 3} {}. The maximum sum among all segments is 4.
• Query 3: Remove the element at index 1 break the current array into {1}, {}. The maximum sum among all segments is 1.
• Query 4: Remove the element at index 2 break the current array into {}, {}. The maximum sum among all segments is 0.

Input: arr[] = {1, 2, 3, 4, 5}, queries[] = {4, 2, 3, 5, 1}
Output: 6 5 5 1 0

Подход: Данная проблема может быть решена с использованием структуры данных Disjoint Set Union. Идея состоит в том, чтобы хранить все запросы в массиве, изначально все элементы находятся в разных наборах, обрабатывать запросы в обратном порядке, для каждого запроса делать операцию объединения для текущего элемента с его левыми и правыми элементами с помощью операции поиска , параллельно отслеживайте максимальный элемент, затем сохраняйте его в массиве, затем печатайте элементы массива в обратном порядке. Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте векторы parent(N + 1) , rank(N + 1, 0) , setSum(N + 1, 0) и currMax .
• Переберите диапазон [1, N+1), используя переменную i , и установите значение parent[i] как -1 и setSum[i] как arr[i – 1] .
• Вставьте значение 0 в вектор currMax[], потому что после последнего запроса ответ будет равен 0 .
• Переберите диапазон [N – 1, 0] в обратном порядке, используя переменную i , и выполните следующие шаги:
  • Если parent[queries[ I ]] равно -1 , установите его как query[i] .
  • Если запросы[i] – 1 >= 0 && parent[queries[i] – 1] != -1 , то вызовите функциональную операцию union(parent, rank, setSum, запросы[ I ], запросы[I]-1) .
  • Если запросы[i] + 1 <= N && parent[queries[i] + 1] != -1, то вызовите функциональную операцию union(parent, rank, setSum, запросы[ I ], запросы[I]+1) .
  • Установите значение maxAns как максимальное значение maxAns или setSum[queries[ I ]] и поместите значение maxAns в вектор currMax[] .
• Переверните вектор currMax[] и напечатайте его значения в качестве ответа.

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

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