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

我在一次面试中遇到了一个算法问题，但我似乎想不出来。我知道它应该如何工作，但无法从算法上进行排序。
所以假设一家公司交易石油桶，一次只能保留一个石油桶。假设公司知道一年中每一天的每桶价格。所以它作为数组传入。怎样才能写出一个算法来找到什么时候买卖？
下面是一个简单化仅5天的例子：
70 74 73 72 76，分别为周一至周五。
这里最好的做法是周一（70日）买入周二（74日）卖出，周四（72日）买入周五（76日）卖出。应该递归地处理这个问题吗？我真的很想解决这个问题。
谢谢，

最佳答案

我想你想最大化你的利润，对吧？
在这种情况下，您只需购买局部极小值，并在局部极大值下进行销售，这将是一个简单的线性搜索。
其实，就是这么简单。证明：
我们来表示

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

have仅在[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)

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

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)

第二行来自have，第三行是对max(x, 0) >= x的简单重写，第四行来自M(i)。
现在，如果我们设置M(i) >= 0，它将获得与上面相同的利润，这意味着它是最大的。同样，这意味着你购买当地极小值，并在当地最大值出售。