"""Leetcode 714. Best Time to Buy and Sell Stock with Transaction Fee
Medium

URL: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/

Your are given an array of integers prices, for which the i-th element is the price of
a given stock on day i; and a non-negative integer fee representing a transaction fee.

You may complete as many transactions as you like, but you need to pay the transaction
fee for each transaction. You may not buy more than 1 share of a stock at a time
(ie. you must sell the stock share before you buy again.)

Return the maximum profit you can make.

Example 1:
Input: prices = [1, 3, 2, 8, 4, 9], fee = 2
Output: 8
Explanation: The maximum profit can be achieved by:
- Buying at prices[0] = 1
- Selling at prices[3] = 8
- Buying at prices[4] = 4
- Selling at prices[5] = 9
The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

Note:
- 0 < prices.length <= 50000.
- 0 < prices[i] < 50000.
- 0 <= fee < 50000.
"""

class Solution(object):
    def maxProfit(self, prices, fee):
        """
        :type prices: List[int]
        :type fee: int
        :rtype: int
        """
        pass


def main():
    pass


if __name__ == '__main__':
    main()

@@ -983,16 +983,18 @@
 Solution
+Dp
 (object)
@@ -1124,55 +1124,790 @@
 int%0A
-        %22%22%22%0A        pass%0A%0A%0Adef main():%0A    pass
+%0A        Time complexity: O(n).%0A        Space complexity: O(n).%0A        %22%22%22%0A        if not prices:%0A            return 0%0A%0A        n = len(prices)%0A%0A        # Before day i, the max profit ending with buy/sell.%0A        profit_buys = %5B0%5D * n%0A        profit_sells = %5B0%5D * n%0A%0A        profit_buys%5B0%5D = -prices%5B0%5D%0A%0A        for i in range(1, n):%0A            profit_buys%5Bi%5D = max(profit_sells%5Bi - 1%5D - prices%5Bi%5D, %0A                                 profit_buys%5Bi - 1%5D)%0A%0A            # Pay transaction fee when sell.%0A            profit_sells%5Bi%5D = max(profit_buys%5Bi - 1%5D + prices%5Bi%5D - fee, %0A                                  profit_sells%5Bi - 1%5D)%0A%0A        return profit_sells%5B-1%5D%0A%0A%0Adef main():%0A    # Output: 8%0A    prices = %5B1, 3, 2, 8, 4, 9%5D%0A    fee = 2%0A    print SolutionDp().maxProfit(prices, fee)
 %0A%0A%0Ai

Complete dp sol