# 22.06.2023 [714. Best Time to Buy and Sell Stock with Transaction Fee]

Max profit from buying stocks and selling them with `fee` for `prices[day]`

22.06.2023

714. Best Time to Buy and Sell Stock with Transaction Fee medium
blog post

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/253

Problem TLDR

Max profit from buying stocks and selling them with fee for prices[day]

Intuition

Naive recursive or iterative Dynamic Programming solution will take O(n2)O(n2) time if we iterate over all days for buying and for selling.
The trick here is to consider the money balances you have each day. We can track two separate money balances: for when we’re buying the stock balanceBuy and for when we’re selling balanceSell. Then, it is simple to greedily track balances:

• if we choose to buy, we subtract prices[day] from balanceBuy

• if we choose to sell, we add prices[day] - fee to balanceSell

• just greedily compare previous balances with choices and choose maximum balance.

Approach

• balances are always following each other: buy-sell-buy-sell.., or we can rewrite this like currentBalance = maxOf(balanceSell, balanceBuy) and use it for addition and subtraction.

• we can keep only the previous balances, saving space to O(1)

Complexity

• Time complexity:
  O(n)

• Space complexity:
  O(1)

Code

    fun maxProfit(prices: IntArray, fee: Int) = prices
        .fold(-prices[0] to 0) { (balanceBuy, balance), price ->
            maxOf(balanceBuy, balance - price) to maxOf(balance, balanceBuy + price - fee)
        }.second