买卖股票 II 图解题解

无限次买卖，最多能赚多少钱

给一个数组 prices，prices[i] 是第 i 天的股价。可以在任意天买入、任意天卖出，还能反复交易，唯一的规矩是买入前手上不能压着没卖掉的股票。问把这些买卖凑到最好，最多赚多少。题面例子 prices=[7,1,5,3,6,4]，答案是 7。

盯着最低价买、最高价卖，为什么只赚 5

第一反应是找全程最低那天买进、最高那天卖出。这串数里最低是 1、它之后的最高是 6，一进一出赚 5。可正确答案是 7，多出 2。差就差在一笔买卖只框得住一次「低进高出」，而这串价格里明明有两段各自向上的行情，硬塞进一笔就丢了其中一段。

为什么把每段上涨都收下，正好是最多

既然不限次数，就别再想「整段一次买卖」，改成盯着相邻两天。看一段上涨 a＜b＜c，从 a 拿到 c 赚的是 (c-a)；把它拆开，(c-a) 正好等于 (b-a) 加 (c-b)——中间那天 b 卖掉再立刻买回，收益一分不差。所以一整段上涨，等价于把段里每一对相邻正差都收下。

推到全程就清楚了：把所有相邻的正差价加起来，覆盖的正是每一段上涨，一段不漏；下跌那些天差价是负的，根本不碰，也就绕开了所有亏损。既没漏掉能赚的、又没沾上会亏的，这个和既是能拿到的上界、也真能拿到。落到每天的动作就是——只要明天比今天高就把这段差价收进口袋、不去纠结更远的价格。

相邻高一格就累加，一遍扫到底

代码就照这个来：利润 profit 从 0 起，下标 i 从第 1 天走到最后一天，只要 prices[i]＞prices[i-1]，就把 prices[i]-prices[i-1] 这段差价加进 profit，不高就跳过，走完返回 profit。全程只从头到尾扫一遍，时间 O(n)；除了一个累加变量不占别的地方，空间 O(1)。不用记住在哪天买、哪天卖，只认相邻的涨跌。

[7,1,5,3,6,4] 逐天比一遍，7 一笔笔落进口袋

从第 1 天起逐天比。1 和昨天 7 比是跌的，跳过，profit 还是 0；5 比昨天 1 高，收下 4，profit=4；3 比昨天 5 低，跳过；6 比昨天 3 高，收下 3，profit=7；最后 4 比昨天 6 低，跳过。走到头 profit=7。

下跌那天最容易也跟着记上一笔——负数会把攒下的利润吃回去，这种天只能跳过。另一个卡点是怕「同一天又买又卖」犯规而不敢累加，可相邻正差从不要求真在同天来回：a＜b＜c 时把 (c-a) 拆成两笔，和一整笔的账完全对得上。

Python

def maxProfit(prices):
    profit = 0
    for i in range(1, len(prices)):
        if prices[i] > prices[i - 1]:
            profit += prices[i] - prices[i - 1]  # 吃进这段上涨
    return profit

C++

int maxProfit(vector<int>& prices){
    int profit = 0;
    for(int i = 1; i < prices.size(); i++){
        if(prices[i] > prices[i - 1])
            profit += prices[i] - prices[i - 1]; // 累加正差
    }
    return profit;
}

Java

public int maxProfit(int[] prices) {
    int profit = 0;
    for (int i = 1; i < prices.length; i++) {
        if (prices[i] > prices[i - 1]) {
            profit += prices[i] - prices[i - 1]; // 吃进这段上涨
        }
    }
    return profit;
}