Максимизировать разницу между суммой четных и нечетных элементов подпоследовательности | Набор 2

Опубликовано: 21 Сентября, 2022

Дан массив arr[] , состоящий из N положительных целых чисел, задача состоит в том, чтобы найти максимальное значение разности между суммой элементов с четными и нечетными индексами для любой подпоследовательности массива.

Note: The value of N is always greater than 1.

Примеры:

Input: arr[] = { 3, 2, 1, 4, 5, 2, 1, 7, 8, 9 } 
Output: 15 
Explanation: 
Considering the subsequences { 3, 1, 5, 1, 9 } from the array 
Sum of even-indexed array elements = 3 + 5 + 9 = 17 
Sum of odd-indexed array elements = is 1 + 1 = 2 
Therefore, the difference between the sum of even and odd-indexed elements present in the subsequence = (17 – 2) = 15, which is the maximum possible.

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

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

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

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

Эффективный подход . Вышеуказанный подход также можно оптимизировать с помощью динамического программирования, поскольку в приведенном выше подходе есть оптимальная подструктура и перекрывающиеся подзадачи. Выполните следующие шаги, чтобы решить данную проблему:

  • Инициализируйте два массива, dp1[] и dp2[] размера N , и инициализируйте значениями -1 , такими что dp1[i] хранит максимальную сумму из подпоследовательности нечетной длины до i -го индекса, а dp2[i] хранит максимальная сумма из подпоследовательности четной длины до i -го индекса.
  • Обновите значение dp1[0] как arr[0] и dp2[0] как 0 .
  • Переберите диапазон [1, N], используя переменную i , и выполните следующие шаги:
    • Обновите значение dp1[i] как dp1[i] = max(dp1[i – 1], dp2[i – 1] + arr[i]) , так как i -й элемент будет добавлен по четному индексу в подпоследовательности . Следовательно, добавляется элемент массива arr[i] .
    • Обновите значение dp2[i] как dp2[i] = max(dp2[i – 1], dp1[i – 1] – arr[i]) , так как i -й элемент будет присоединен к нечетному индексу в подпоследовательности. Следовательно, элемент массива arr[i] вычитается.
  • После выполнения вышеуказанных шагов выведите в качестве результата максимум (dp1[N – 1], dp2[N – 1]) .

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

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

Оптимизированный подход. Описанный выше подход можно дополнительно оптимизировать, используя две переменные, odd и even , вместо двух массивов, dp1[] и dp2[] , чтобы сохранить максимальную разницу между суммой элементов с четными и нечетными индексами. Для каждого индекса i требуются только максимальные суммы подпоследовательностей четной и нечетной длины предыдущего индекса для вычисления текущих состояний.

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

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

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