# 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_wrong(self, prices, fee):
        """
        :type prices: List[int]
        :type fee: int
        :rtype: int
        """
        st, buy, res = [], prices[0], 0
        prices.extend([0])

        for p in prices:
            if buy > p:
                if st:
                    res += st.pop() - buy - fee
                buy = p
            elif not st:
                if p > buy + fee:
                    st.append(p)
            else:
                if p > st[-1]:
                    st.pop()
                    st.append(p)
                else:
                    res += st.pop() - buy - fee
                    buy = p
        return res

    def maxProfit_greedy(self, prices, fee):
        """
        :type prices: List[int]
        :type fee: int
        :rtype: int
        """
        # buy - cost of buy stock, at the first day, buy = prices[0]
        res, buy = 0, prices[0]
        for p in prices:
            # if current price is < buy, there is no profits. also, because we are greedy
            # we abandon the prev value of buy, buy current stock should be more profitable
            if p < buy:
                buy = p
            else:
                # cur price is profitable
                if p > buy + fee:
                    # profits if I sell at this day
                    res += p - buy - fee
                    # this code is very hard to understand
                    # 3 case:
                    # case 1 - [1,2,3,5,8,14,15],2, the best solution is 15-1-2 = 12
                    # but when code arrive 8, we sell it, got some profits
                    # but should I buy back stock at price 8, and sell it again? no, you should not
                    # because buy back and sell it again for higher price make you pay extra fee
                    # when we arrive to 14, if we buy back 8, then sell it again, we can only earn
                    # 14-8-2 = 4, in fact, we should not sell at 8, we should sell at 14 directly
                    # so we do p-fee in advance, then for someday later, when we do p1-(p-fee)-fee, we
                    # won't charged by extra fee
                    # also you can see for next loop, if p < buy, means when p is small enough, then we need
                    # to start a new transaction, otherwise, we continue the transaction.
                    # so when we arrive 8, res = 8-1-2 = 5, buy = 6,
                    # arrive 14, res = 5 + 14-6-2 = 5+6=11, actually = 14-1-2=11

                    # case 2 - [1, 3, 2, 8, 4, 9], 2
                    # when we reach 8, res = 8-1-2=5, buy = 6
                    # then reach 4, 4 < 6, it worth to start a new transaction and pay extra fee

                    # case 3 - [1,3,2,8,7,10]
                    # when we reach 8, res = 5, buy = 6, but p = 7 > buy, so it not worth to start a new transaction
                    # we keep this buy until we meet a higher price to continue transaction or lower price to start new
                    # transaction
                    buy = p - fee
        return res

    def maxProfit_dp(self, prices, fee):
        """
        :type prices: List[int]
        :type fee: int
        :rtype: int
        """
        N = len(prices)
        # sell[i], max profit sell at ith day
        # hold[i], max profit buy at ith day
        sell, buy = [0] * N, [0] * N
        buy[0] = -prices[0]

        for i in xrange(1, N):
            # if I sell at ith day, 2 case:
            # case 1 - at (i-1)th day, I hold some stocks, and sell at next day, got price[i] - fee
            # case 2 - we may sell at i-1 th day, if it is even larger than case 1, why sell it
            sell[i] = max(sell[i - 1], buy[i - 1] + prices[i] - fee)
            # if I buy at ith day, 2 case
            # case 1 - I make a sell at i-1 th day, then buy at ith day,
            # case 2 - the profit I bought at i-1 th day, and at ith day, I didn't buy any stock
            buy[i] = max(buy[i - 1], sell[i - 1] - prices[i])

        return sell[-1]

    def maxProfit_dp2(self, prices, fee):
        """
        :type prices: List[int]
        :type fee: int
        :rtype: int
        """
        N = len(prices)
        hold, sell = -prices[0], 0

        for i in xrange(1, N):
            sell = max(sell, hold + prices[i] - fee)
            hold = max(hold, sell - prices[i])

        return sell


if __name__ == '__main__':
    print Solution().maxProfit_greedy([1, 3, 2, 8, 14, 15], 2)
    print Solution().maxProfit_greedy([1, 3, 2, 8, 4, 9], 2)
    print Solution().maxProfit_greedy([1, 2, 3, 4, 5, 6, 7, 8], 2)
    print Solution().maxProfit_greedy([1, 3, 5, 9, 6, 2, 6, 3, 7], 2)
    print Solution().maxProfit_greedy([1, 3, 7, 5, 10, 3], 3)

    print Solution().maxProfit_dp([1, 3, 2, 8, 4, 9], 2)
    print Solution().maxProfit_dp([1, 2, 3, 4, 5, 6, 7, 8], 2)
    print Solution().maxProfit_dp([1, 3, 5, 9, 6, 2, 6, 3, 7], 2)
    print Solution().maxProfit_dp([1, 3, 7, 5, 10, 3], 3)

    print Solution().maxProfit_dp2([1, 3, 2, 8, 4, 9], 2)
    print Solution().maxProfit_dp2([1, 2, 3, 4, 5, 6, 7, 8], 2)
    print Solution().maxProfit_dp2([1, 3, 5, 9, 6, 2, 6, 3, 7], 2)
    print Solution().maxProfit_dp2([1, 3, 7, 5, 10, 3], 3)
