最佳买卖股票时间 II

给你一个数组 prices，prices[i] 是第 i 天股票的价格。

找到你能获取的最大收益。你可以按你喜欢的方式进行多次交易（多次买入和卖出同一只股票）。

注意： 你不能同时进行多项交易（即你在买入之前要先把之前的持有的股票卖出）。

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.

Example 2:

Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.

Example 3:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e., max profit = 0.

限制:

1 <= prices.length <= 3 * 10⁴
0 <= prices[i] <= 10⁴

解法假设 cost1、profit1 分别为（至多进行）一次交易时最低的成本和最高利润，cost2、profit2 分别为（至多进行）两次交易时最低的成本和最高利润，price 为价格，x 为当前天数，则有以下方程： $$ \begin{cases} cost1(x) &=& min(cost1(x - 1), & price(x)) \

profit1(x) &=& max(profit1(x-1), & price(x) - cost1(x)) \

cost2(x) &=& min(cost2(x-1), & price(x) - profit1(x) ) \

profit2(x) &=& max(profit2(x-1), & price(x) - cost2(x))
\end{cases} $$

根据状态转移方程代码实现：

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    if (!prices.length) return 0;

    let cost1 = prices[0];
    let cost2 = prices[0];
    let profit1 = 0;
    let profit2 = 0;
    
    for (let i = 0; i < prices.length; i++) {
        const price = prices[i];
        
        cost1 = Math.min(cost1, price);
        profit1 = Math.max(profit1, price - cost1);
        
        cost2 = Math.min(cost2, price - profit1);
        profit2 = Math.max(profit2, price - cost2);
    }
    
    return profit2;
};