面试问题:最大多次销售利润

Question

我在面试中遇到的算法问题上有一个问题,我似乎无法弄明白.我理解它应该如何工作,但无法通过算法对其进行排序.

因此,假设一家公司交易油桶,并且一次只能保留一个油桶.假设公司知道一年中每天的每桶价格.所以它作为一个数组传递.如何编写算法来查找何时买卖？

以下是简化为期5天的示例: 70 74 73 72 76分别为星期一至星期五.

这里最好的事情是周二(74)周二买入卖出(74)然后周四买入(72)并在周五卖出(76).应该递归接近吗？我真的想解决这个问题.

谢谢,

Answer 1

我想你想要最大化你的利润,对吗？

在这种情况下,您只需购买本地最小值并以当地最大值出售,这将是一个简单的线性搜索.

实际上,就是这么简单.证明:

我们来表示

p(i) ... the price of oil on day i
have(i) ... 1 if we retain the barrel overnight from day i to day i+1, 0 otherwise

只有[0,N-1]中的i定义了

现在,如果我们在白天购买并在当天k销售l,我们就有了

have(k) = 1
have(l) = 0
have(i) = 1 for k < i < l

利润将是

p(l)-p(k) = sum over {i from k to l-1} (p(i+1)-p(i))

我们来表示

M(i) = max(p(i+1) - p(i), 0)

对于所有可能的布尔函数have,我们有

profit(have) = sum over {i where have(i)==1} (p(i+1) - p(i))
 <= sum over {i where have(i)==1} max(p(i+1) - p(i), 0)
 <= sum over {i where have(i)==1} M(i)
 <= sum over {i in [0, N-1]} M(i)

第二行来自这样一个事实:max(x, 0) >= x第三行是简单的重写M(i),第四行来自M(i) >= 0.

现在,如果我们设置have(i) == (p(i+1)>p(i)),它将具有与上面相同的利润,这意味着它是最大的.此外,这意味着您以当地最低价购买并以当地最高价出售.