讨论/题目交流/求差价最优值/
求差价最优值

给定一个price数组,表示商品每天的价格,商人可以在i天买入该商品放入库房,j天卖出,所得利润为价格差减去保管费,费用每天1元,即j-i,j>=i,求最优收益。

这道题第一思路是用动态规划,奈何一直写不出最优解,大家有啥好招吗?

展开讨论
共 4 个讨论

记录两个中间变量,一个是已经扫描过的price数组中price[i]-i的最小值,另一个是price[j]-j再减去前面那个最小值之后的最大值,即当前的最大利润。然后逐个扫描一遍就可以了

1

最小值为0,不买不卖

动态规划中关于数组求最优解的情况,我个人觉得一般两个方向:一,F(i)存储之前已经计算过的值,二,F(i)表示下标<=i情况下的最优解。
这道题你可以按情况2理解,F(i)=max(price[j]-price[k],F(i-1))-(j-k-1),且i>=j>=k。
你可以在草稿纸上画一个dp数组,然后按照计算F(i)的方法往里面填数据,找几个例子测一下如果ok就写成代码再测一下

这和力扣的股票买卖题一样,栈的思路,维持一个最小值,遇到更大值时,记录利润,遇到更小值时,更新最小值…