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

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

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

Примеры:

Input: arr[] = {1, 2, 6, 8, -5, 10}
Output: 14
Explanation: Considering the subsequence {1, 8, -5, 10} which satisfies the given condition, sum of the subsequence = (1 + 8 – 5 + 10) = 14, which is the maximum possible sum.

Input: arr[] = {1, -1, 1, -1}
Output: 1

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

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

Эффективный подход. Описанный выше подход также можно оптимизировать с помощью динамического программирования, поскольку он имеет перекрывающиеся подзадачи и оптимальную подструктуру. Подзадачи могут быть сохранены в таблице dp[][] с использованием мемоизации, где dp[i][prev] хранит максимально возможную сумму от i-й позиции до конца массива, когда четность предыдущего выбранного числа равна 'prev' . Для каждого состояния есть 2 случая:

  • Включить текущий элемент, если четность отличается от предыдущего элемента.
  • Не включать текущий элемент.

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

  • Определите рекурсивную функцию maxSum(i, prev, is_selected) , выполнив следующие шаги:
    • Проверьте базовые случаи, если значение i равно N , верните 0 , или если значение i равно N – 1 и is_selected равно false , верните arr[i] .
    • Если результат состояния dp[i][prev] уже вычислен, вернуть это состояние dp[i][prev] .
    • Если четность текущего элемента отличается от prev , то выберите текущий элемент как часть подмножества и рекурсивно вызовите функцию maxSum для элемента с индексом (i + 1) .
    • Пропустите текущий элемент для текущего подмножества и рекурсивно вызовите функцию maxSum для index (i + 1) .
    • Возвращает максимальное значение двух случаев из текущих рекурсивных вызовов.
  • После выполнения вышеуказанных шагов выведите в качестве результата значение maxSum(0) .

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

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

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