买卖股票含手续费 图解题解

反复买卖还要交手续费，什么时候动手反而亏钱

给数组 prices，prices[i] 是第 i 天股价，另有固定手续费 fee，卖出扣一笔。可反复买卖，但同时最多持一股，想再买得先卖，求最大利润。题面 prices=[1,4,2,7,3,2,5,1,6]、fee=2，答案 8。难在手续费：差价太小时赚的不够交费，动手反亏。

把每天买卖不动都枚举一遍，为什么撑不住

暴力是每天买、卖、不动三选一全枚举挑最高。可 n 天就是 3 的 n 次方量级，稍多就跑不完。决定明天怎么选的只有此刻手里有没有股，把它记下来、每种只算一次，指数枚举就压成一趟线性递推（拿前面算好的值推后面）。

持股、空仓两个状态，各自记的是账上多少钱

每天收盘只两种状态：持股或空仓。两个变量记这两态的最大现金——hold 记收盘持股时最多剩多少，cash 记收盘空仓时最多剩多少。hold 通常为负，买入先垫钱，第 0 天以 1 元买那股账上成 -1。开局 hold=-prices[0]、cash=0。

两态怎么互相转移，手续费为什么只在卖出扣一次

每态两条来路取更划算的。持股要么接着拿旧 hold，要么今天买——昨天空仓掏 prices[i]，取 hold=max(hold, cash-prices[i])。

空仓要么接着空旧 cash，要么今天卖——昨天持股以 prices[i] 卖出、加回股价再扣 fee，取 cash=max(cash, hold+prices[i]-fee)。

手续费只在卖出扣一次：一趟买卖收一次费，买入只垫股价，卖出才结清，两头都扣就交两回。

拿题面 fee=2 的示例逐天填两行

开局第 0 天价 1，hold=-1、cash=0。第 1 天价 4：hold=max(-1,0-4)=-1，cash=max(0,-1+4-2)=1。第 2 天价 2：hold=max(-1,1-2)=-1，cash=max(1,-1+2-2)=1。第 3 天价 7：hold=max(-1,1-7)=-1，cash=max(1,-1+7-2)=4。第 4 天价 3：hold=max(-1,4-3)=1（4 即第 3 天的 cash），cash=max(4,1+3-2)=4。第 5 天价 2：hold=max(1,4-2)=2，cash=max(4,2+2-2)=4。第 6 天价 5：hold=max(2,4-5)=2，cash=max(4,2+5-2)=5。第 7 天价 1：hold=max(2,5-1)=4，cash=max(5,4+1-2)=5。第 8 天价 6：hold=max(4,5-6)=4，cash=max(5,4+6-2)=8。空仓 cash=8 即最大利润。

答案为什么取空仓、hold 初值又设成负数，复杂度多少

每天两次取大，一遍 O(n)；只留 hold、cash 两变量滚动，空间 O(1)。

买入别扣费——fee 只在卖出减这一次，两头都扣等于一趟交两回。hold 初值也别写成 0：第 0 天持股账上已垫掉买入价，初值得是 -prices[0]，写 0 相当于白得一股。最后返回 cash 别返回 hold，收盘还攥着股票的钱没落袋，永远不会更优。

Python

def maxProfit(prices, fee):
    hold, cash = -prices[0], 0
    for p in prices[1:]:
        hold = max(hold, cash - p)
        cash = max(cash, hold + p - fee)
    return cash

C++

int maxProfit(vector<int>& prices, int fee){
    long hold = -prices[0], cash = 0;
    for(size_t i=1;i<prices.size();i++){
        hold = max(hold, cash - prices[i]);
        cash = max(cash, hold + prices[i] - fee);
    }
    return cash;
}

Java

int maxProfit(int[] prices, int fee){
    int hold = -prices[0], cash = 0;
    for(int i = 1; i < prices.length; i++){
        hold = Math.max(hold, cash - prices[i]);
        cash = Math.max(cash, hold + prices[i] - fee);
    }
    return cash;
}