714_Best Time to Buy and Sell Stock with Transaction Fee

Your are given an array of integersprices, for which thei-th element is the price of a given stock on dayi; and a non-negative integerfeerepresenting 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:

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.

Solution

Idea: the idea is similar to that of buy and sell stock with unlimited time. Only the condition when a new transaction starts is different because of the fee. the new condition is :

• When the current price is larger than previous maximum price - fee and larger than minimum price, update the maximum price with the maximum of itself and the current price

• Otherwise,

  • When the current price is smaller than the minimum price, start a new transaction

  • When the current price is smaller than previous maximum price - fee, start a new transaction

Time Complexity: $O(n)$

Space Complexity: $O(1)$

def maxProfit(self, prices, fee):
    """
    :type prices: List[int]
    :type fee: int
    :rtype: int
    """
    if len(prices) < 2 :
        return 0

    min_price = prices[0]
    max_price = prices[0]
    profit = 0

    for i in range(1, len(prices)) :   
        if prices[i] > max_price - fee and prices[i] > min_price:
            max_price = max(prices[i], max_price)
        else :
            profit += max(max_price - min_price - fee, 0)
            max_price = prices[i]
            min_price = prices[i]
    profit += max(max_price - min_price - fee, 0)    
    return profit