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) 去取得元素在三种状态下收益最大的状态
题目
给定一个整数数组,其中第 i 个元素代表了第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):
你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。 卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。 示例:
解题代码
解题思路
代码效率
执行用时: 76 ms , 在所有 JavaScript 提交中击败了 64.56% 的用户 内存消耗: 36.7 MB , 在所有 JavaScript 提交中击败了 100.00% 的用户