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

佚名 6年前 (2018-10-08) 算法 1685人围观抢沙发百度已收录

问题

给定一个数组，第i个元素表示第i天股票的价格，可执行多次“买一次卖一次”，每次执行完（卖出后）需要小费，求最大利润

Input: prices = [1, 3, 2, 8, 4, 9], fee = 2
Output: 8
Explanation: ((8 - 1) - 2) + ((9 - 4) - 2) = 8
SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

思路和代码

在某天交易（或选择不操作）之后，有两个状态，要么手有股票，要么手中没有股票，我们用两个状态数组来表示。hava_stock表示有股票，no_stock表示没有股票。

have_stock[i]表示第i天结束后（此时手中有股票）最大利润。
no_stock[i]表示第i天结束后（此时手中没股票）的最大利润。

如果当天操作结束后，你手头没有股票的话，那么你：要么是今天卖了股票（昨天是有股票的），要么是保持了昨天的状态，只需要在这两者取最大即可。no_stock[i] = max(have_stock[i-1]+prices[i]-fee, no_stock[i-1])。

如果当天操作结束后，你手头有股票的话，那么你：要么是今天买了股票（昨天是没有股票的），要么是保持了昨天的状态，只需要在这两者取最大即可。have_stock[i] = max(no_stock[i-1]-prices[i], have_stock[i-1])。

返回最后一天的no_stock即可，因为完成交易获得最大利润时，手头肯定是没有股票的。

时间复杂度O(n)，空间复杂度O(n)

class Solution(object):
    def maxProfit(self, prices, fee):
        """
        :type prices: List[int]
        :type fee: int
        :rtype: int
        """
        no_stock = [0]*len(prices)
        have_stock = [0]*len(prices)
        have_stock = -prices[0]
        for i in range(1,len(prices)):
            no_stock[i] = max(have_stock[i-1]+prices[i]-fee, no_stock[i-1])
            have_stock[i] = max(no_stock[i-1]-prices[i], have_stock[i-1])
        return no_stock[len(prices)-1]

优化

由于两个dp数组中状态都取决于前一天，可以进行优化，省去dp数组开销。

对于no_stock的max计算，直接去掉数组索引，计算前的变量have_stock[i-1]和no_stock[i-1]表示前一天的，直接写成have_stock和no_stock即可，计算后的变量no_stock[i]表示今天的，写成no_stock即可。
对于have_stock的max计算，have_stock[i-1]也可以直接写成have_stock表示前一天的，而no_stock[i-1]不能写成no_stock，因为在上一步计算（no_stock的计算中可能覆盖了），所以可以用一个tmp在no_stock计算之前暂存起来。

tmp = no_stock
no_stock = max(have_stock+prices[i]-fee, no_stock)
have_stock = max(tmp-prices[i], have_stock)

事实上这个临时变量也可以省去。考虑no_stock的max操作，当no_stock较大时当然不需要用tmp来暂存前一天的no_stock，因为前一天跟今天的一样。而have_stock+prices[i]-fee较大时可以得到have_stock > no_stock - prices[i]，此时have_stock的max计算会直接取到have_stock，不会用到no_stock，所以不用担心no_stock被改变后影响have_stock的max计算。

时间复杂度O(n)，空间复杂度O(1)

class Solution(object):
    def maxProfit(self, prices, fee):
        """
        :type prices: List[int]
        :type fee: int
        :rtype: int
        """
        no_stock = 0
        have_stock = -prices[0]
        for i in range(1,len(prices)):
            no_stock = max(have_stock+prices[i]-fee, no_stock)
            have_stock = max(have_stock, no_stock-prices[i])
        return no_stock