<分区>
是否有比 O(n²) 更好的解决方案来解决以下问题:
第i天,商品单价为B[i],可卖S[i]个单位.如果你在第 1 天有 1 个单位的现金,在你永远不能卖掉当天没有的股票的限制下,你在 N 天能赚多少钱?
<分区>
是否有比 O(n²) 更好的解决方案来解决以下问题:
第i天,商品单价为B[i],可卖S[i]个单位.如果你在第 1 天有 1 个单位的现金,在你永远不能卖掉当天没有的股票的限制下,你在 N 天能赚多少钱?
最佳答案
只是修改之前的重复。
C[i]: cash we can have at end of the day i.
C[i] = max(C[i-1],(S[i]-B[i])*G[i]);
在哪里
G[i] is unit of good we can afford to buy.
G[i]=floor(C[i-1]/B[i])
关于algorithm - 解决买卖优化问题,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4128487/