经典的最大化股票利润问题涉及一个包含股票价格的数组,您需要返回可以获得的最大利润:
我理解给定股票报价最大化利润的逻辑。以一种简单的方式,我们可以维护一个 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。
谢谢