Максимизируйте удаления, удалив префикс и суффикс массива с той же суммой

Опубликовано: 25 Февраля, 2023

Учитывая массив Arr[] размера N , стоимость удаления i- го элемента равна Arr[i] . Задача состоит в том, чтобы удалить максимальное количество элементов, удалив префикс и суффикс одинаковой длины и имеющих одинаковую общую стоимость.

Примеры:

Input: Arr[] = {80, 90, 81, 80}
Output: 2 
Explanation: If we choose 80 from front ( left side cost = 80),  
and choose 80 from back (right side cost = 80), both are same.
But when we choose 90 from front or 81 from back 
the costs would not remain same. 
So maximum 2 elements can be removed from the array.

Input:  Arr[] = { 8, 5, 7, 8, 7, 6, 7}
Output: 6
Explanation: It will be optimal to select 8, 5, 7 from the front 
( left side cost = 20), and 7, 6, 7 from the back (right side cost = 20),  
which results in a maximum of 6 elements ( {8, 5, 7}, {7, 6, 7} ) 
that can be removed from the array.

Подход: Для решения задачи используйте следующую идею:

Since we have to equalize the cost of removing elements, we should know the sum of costs from both ends. Sum needs to be calculated from front and back for each element, so prefix sum and suffix sum can be used to store the sums from both ends.

Then traverse the suffix sum array and find the lower bound if the same in the prefix sum array. The maximum number of elements found is the required answer.

Следуйте приведенной ниже иллюстрации для лучшего понимания.

Иллюстрация :

Consider the array Arr[] = {8, 5, 7, 8, 7, 6, 7}

Prefix sum array = {8, 13, 20, 28, 35, 41, 48}
Suffix sum array = {48, 40, 35, 28, 20, 13, 7} 

For 7 in suffix array:
        => The lower bound is 8 in the prefix array.
        => No elements can be deleted.

For 13 in suffix array:
        => The lower bound is 13 in the prefix array.
        => Elements deleted = 2 + 2 = 4.

For 20 in suffix array:
        => The lower bound is 20 in the prefix array.
        => Elements deleted = 3+3 = 6.

For 28 in suffix array:
        => The lower bound is 28 in the prefix array.
        => The index for both of them is same, that is the same element is considered twice.

Hence maximum 6 elements can be deleted.

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

  • Инициализируйте массив суммы префиксов и сумм суффиксов размером N и назначьте каждый их элемент равным данному элементу массива.
  • Вычислите сумму префикса и сумму суффикса и сохраните их в соответствующих массивах.
  • перебрать массив сумм суффиксов с конца:
    • Выполните нижнюю границу массива сумм префиксов для этой суммы.
    • Получите индекс нижней границы.
    • Если значение нижней границы и сумма суффиксов совпадают, подсчитайте общее количество удаленных элементов.
  • Обновите ответ, чтобы сохранить максимальное количество элементов.

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

Временная сложность: O(N * logN)
Космическая сложность: O(N)

РЕКОМЕНДУЕМЫЕ СТАТЬИ