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