1

经典的最大化股票利润问题涉及一个包含股票价格的数组，您需要返回可以获得的最大利润：

我理解给定股票报价最大化利润的逻辑。以一种简单的方式，我们可以维护一个 running min 和一个 running max_so_far 并检查当前 elem 是否小于 min 或当前 elem - running min 大于 max_so_far 如果是，我们更新我们的 max_so_far

我们最终返回我们的 max_so_far，这是可以获得的最大利润。

现在，我们如何解决 2 shot strategy 的问题？基本上你需要返回 i0, j0, i1, j1 使得 arr[j0]-arr[i0] 和 arr[j1]-arr[i1] 的总和是最大的并且 i0<j0 < i1 <j1

我能够在一定程度上思考，但后来无法弄清楚如何概括它。因此，首先我可以获得包含所有 max_so_far 元素的单次解决方案数组。同样，我可以做一个类似的数组，但从 arr[n-1] 开始到 0。这告诉我如果我必须在今天之后卖出，我可以赚取的最大利润是多少。如果我在前向迭代中添加数组中的相应元素，并在后向迭代中添加数组中的对应元素，并且从中得到最大元素，则对应于 max i0,j0,i1,j1

但是有人可以先解释一下k-shot算法的逻辑。我想我会想了解 k-shot 策略，以了解如何将 2-shot 策略扩展到 k-shot。

谢谢

4

1 回答 1

0

一种概括是保留一个 2k+1 元素数组，其中第 j个条目（从零开始计数）是在 j 次交易交替买卖之后手头的最大现金。如果 j 是偶数，那么下一个交易就是买入。如果 j 是奇数，则下一笔交易是卖出。

最初，数组为 0，-inf，-inf，...，-inf（负无穷大表示该条目不可行）。当下一个价格 p 出现时，按如下顺序更新索引 2k、2k-1、...、1 处的元素。2k 的最佳交易是 (i) 上一个条目的最大值，表示 2k 之前的交易 (ii) 2k-1 的条目加上 p，表示 2k-1 之前的交易，然后在 p 处出售。2k-1 的最佳交易是 (i) 前一个条目的最大值，表示 2k-1 个之前的交易 (ii) 2k-2 的条目减去 p，表示 2k-2 个之前的交易，然后在 p 处购买。继续交替加减。

我将把恢复买入/卖出时机的问题留作练习。

于 2013-08-13T00:27:25.857 回答