309. 最佳买卖股票时机含冷冻期 https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/

[AmelloAster]

题目

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。​

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
示例:

输入: [1,2,3,0,2]
输出: 3 
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

解题代码

var maxProfit = function (prices) {
    let sold = 0;
    let hold = -Infinity;
    let rest = 0;

    for(let i of prices){
        let pres = sold;
        let preh = hold;

        hold = Math.max(preh, rest - i);
        sold = preh + i
        rest = Math.max(rest, pres)
    }

    return  Math.max(rest, sold)

}

解题思路

假设每个元素有三种状态
hold sold rest
假如当前元素为 hold 状态 那么 hold 时的收益 = max(prehold, rest - price)
也就是之前已经持有过股票的收益 和 卖出股票处于冷冻期的收益减去现在购入股票的收益做比较
假如当前元素为 sold 状态 那么 sold 时的收益 = prehold + price 
也就是之前持有股票的收益 + 现在卖出股票的收益
假如当前元素为 rest 状态 那么 rest 时的收益 = max(rest, presold)
也就是之前处于冷冻期的收益 和 之前卖出股票的收益作比较

最后 max(hold, sold, rest) 去取得元素在三种状态下收益最大的状态

 

代码效率

执行用时：
76 ms , 在所有 JavaScript 提交中击败了 64.56% 的用户
内存消耗：
36.7 MB , 在所有 JavaScript 提交中击败了 100.00% 的用户