Python solution with detailed explanation


  • 0
    G

    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
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.