algorithm - 可获得的最大利润 - 买入和卖出

Question

假设我们准确预测了 N 天内梅西的价格。预测以列表形式给出，其中 p_i 表示玩家在第 i 日的价格。鲍勃计划在此期间进行多次、连续的交易，但一次不能拥有超过一名梅西，因此需要在再次购买他之前出售他。

鲍勃一开始的预算B有限，无法购买超出他承受能力的梅西。当然，鲍勃可以将他从买卖梅西获得的任何利润添加到他的预算中。对他来说幸运的是，有时他会事先打开随机礼品包，从梅西开始。

最后鲍勃只想获得尽可能多的利润，并出售他最后的梅西。

---

输入格式:

在输入文件的第一行，您会发现 3 个整数，N、B 和 M。

N 代表鲍勃预测梅西价格的天数。 B 代表 Bob 的初始预算。 M可以是0或1；如果鲍勃开始时没有初始梅西可供出售，则为 0；如果他开始时有初始梅西可供出售，则为 1。

在下一行你会发现 N 个整数:p1, p2, ... , pN，用空格分隔，其中 pi 代表梅西在第 i 天的价格。

---

给定测试用例

测试 1

7 5 0

20 10 30 5 10 10 20

正确答案:15

解释:Bob 的初始预算为 5，并且没有初始的 Messi 可供出售。在梅西的价格降到 5 之前他无法购买任何梅西，因此他的利润只有 (20-5) = 15

---

测试 2

7 0 1

20 10 50 80 60 20 10

正确答案:90

说明: 鲍勃的初始预算为 0，并出售 1 个梅西。因此他以 20 的价格出售最初的梅西，以 10 的价格买回他并以 80 的价格出售他，所以他的利润为 20 + (80-10) = 90

---

这个问题是在面试中向我提出的，但我无法提供有效的解决方案。与此同时，我发现了这个问题的一些更简单的变体，例如 Maximum profit by buying and selling a share at most twice ，但我一直没能理解如何使这种思维适应我的问题。

到目前为止，我只能想出一个强力解决方案，该解决方案远远超出了我给出的时间限制(C++ 为 0.1 秒，其中 1 <= N <= 10^5)。

我正在寻找解决方案和思考此类问题的方法，我似乎找不到正确的方法来思考这个问题。

Answer 1

我们可以使用动态规划。

1. 让我们将 f0(i) 定义为如果当天开始时没有梅西 i 时我们可以获得的最大预算。 让 f1(i) 为相同的值，以防我们找到他。

2. i = 0 的基值取决于我们是否一开始就有他。

3. 转换过程如下:

   • 我们可以从 i 到 i + 1 并且什么也不做

   • 如果我们有梅西，我们可以卖掉他(设置f0(i + 1) = max(f0(i + 1), f1(i) + Price(i)) )

   • 如果我们没有他并且我们的预算足够大，我们可以买他 (执行f1(i + 1) = max(f1(i + 1), f0(i) - Price(i)))

4. 答案是f0(n)(这意味着所有日子都过去了，我们却没有他了)。

这个解决方案显然需要线性的时间和空间，所以任何 合理的 C++ 实现应该符合您的要求。