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

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

Примеры:

Input: arr[] = {6, 1, 7, 2, 8, 4}, transactionFee = 2
Output: 8
Explanation: 
A maximum profit of 8 can be obtained by two transactions.
Transaction 1: Buy at price 1 and sell at price 7. Profit = 7 – 1 – 2 = 4.
Transaction 2: Buy at price 2 and sell at price 8. Profit = 8 – 2 – 2 = 4.
Therefore, total profit = 4 + 4 = 8, which is the maximum possible.

Input: arr[] = {2, 7, 5, 9, 6, 4}, transactionFee = 1
Output: 7

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

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

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

buy = max(sell – arr[i], buy)
sell = max(buy +arr[i] – transactionFee, sell)

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

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