题目:给定一个股票价格数组prices,标记了每天股票的价格,还有一个股票买卖手续费fee。求交易最大利润。

比如:

Input: prices = [1, 3, 2, 8, 4, 9], fee = 2
Output: 8

思路:动态规划,使用两个变量分别记录当前购买股票hold和售出股票cash获得的利润。

cash计算很简单,当前股票卖出的时候只要是赚的,就可以出售,递推式也就是:

cash = Math.max(cash, hold + prices[i] - fee)

hold的要求很简单,不要买亏就好了,那么递推式就是:

hold = Math.max(hold, cash - prices[i])

不知道这么说是否直观,可以根据例子来推算一下:

第一天的假设我们买了,cash = 0, hold = -1

第二天会发现,卖出股票减去手续费,没有赚,并且换一支持股,也更亏,那么第二天可以略过。

第三天同第二天。

第四天,很重要的一天。卖出股票减去手续费可以赚5块,那么直接卖。然后再买股票,那么持有股票的金额就为1元。

第五天,最后一天。卖出股票减去手续费可以赚7块,也卖掉。最后手中持有的钱就为8块了。

最后代码如下,JS实现:

var maxProfit = function(prices, fee) {
    let hold = -prices[0], cash = 0;
    
    for (let i = 1; i < prices.length; i++) {
        cash = Math.max(cash, hold + prices[i] - fee);
        hold = Math.max(hold, cash - prices[i]);
    }
    
    return cash;
};

 


0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注