algorithm - 面试题: Maximum multiple-sell profit

Question

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

因此假设一家公司交易石油桶并且一次只能保留一个石油桶。假设公司知道一年中每一天的每桶价格。所以它作为一个数组传入。如何编写一种算法来确定何时买入和卖出？

为了简化，这里有一个仅 5 天的示例:70 74 73 72 76，分别代表周一到周五。

这里最好的做法是在星期一 (70) 买入，在星期二 (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

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)

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

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))，它将具有与上面相同的利润，这意味着它是最大的。此外，这意味着您以局部最小值买入并以局部最大值卖出。