Подпоследовательность максимальной суммы, состоящая из последовательных элементов разной четности
Дан массив 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)