Best Time to Buy and Sell Stock II

122. 买卖股票的最佳时机II

分析

如果今天的股票价格比昨天高，就可以将这部分差价计入利润。这样相当于在每个上升区间都进行买入和卖出操作。将所有上涨的差价累加，即可获得最大利润

为什么这样是最优的？

股票可以在同一天买入和卖出，相当于在每个上涨区间及时买卖。
比如：[1, 2, 3, 4, 5]，买入 1 卖出 5 的利润和每天买卖 (1→2，2→3，3→4，4→5) 是相等的

时间复杂度

时间复杂度 O(n)

空间复杂度

空间复杂度为 O(1)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


class Solution
{
public:
    int maxProfit(vector<int>& prices)
    {
        int res = 0;  // 初始化总利润
        for (int i = 1; i < prices.size(); ++i)  // 遍历价格数组
            if (prices[i] > prices[i - 1])  // 如果今天比昨天贵
                res += prices[i] - prices[i - 1];  // 累加差价利润
        return res;  // 返回总利润
    }
};