**Best Time to Buy and Sell Stock with Transaction Fee** https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/description/

**DP solution building on two choices**

- dp[i] gives the maximum profit possible after day i.
- On day i, we have two choices. Either we can hold the stock or we can make a transaction on day i.
- If we decide to hold, then the maximum profit on day i is same as dp[i-1].
- If we do a transaction, then we are selling at prices[i]. Now for the stock we are selling, say we bought at day j (ranging from 0 to i-1). Then the profit at day i is: max(prices[i]-fee-prices[j]+dp[j-1])
- dp[i] = max(hold, transact) = max(dp[i-1], prices[i]-fee + max(dp[j-1]-prices[j])) j in [0, i-1]
- Note, we can maintain a running maximum for (dp[j-1]-prices[j]). This makes the algorithm O(N) and O(1).

```
class Solution(object):
def maxProfit(self, prices, fee):
"""
:type prices: List[int]
:type fee: int
:rtype: int
"""
profit, max_diff = 0, float('-inf')
for i in range(len(prices)):
hold = profit
transact = prices[i] - fee + max_diff if i > 0 else 0
max_diff = max(max_diff, profit-prices[i])
profit = max(hold, transact)
return profit
```