卖出/买入股票的最大利润，但我们最多只能拥有k股的绝对值

Question

我有一个经典的面试问题要问，但它有一个转折点：

您将获得

n

天的股票价格，

a1, a2, ..., an

。您还将获得一个整数

1 <= k <= n

。每天，您可以做三件事之一：

1. 什么也不做
2. 以当天的价格出售一单位股票。 （即使您的投资组合中没有任何股票，只要您的负债不超过

   k

   股票，您也可以出售）
3. 以当天价格购买一单位股票。

但是，您在任何时候最多可以拥有

k

股股票，或者您最多可以持有

k

股股票。 因此，举例来说，如果您拥有

k

股票，您可以 不 购买更多股票而不出售一些股票。找出你能获得的最大利润。另一个例子是，如果您已经

k

股票负债累累，那么您就无法在不购买一些股票的情况下出售更多股票。

您希望在第n天之后拥有

净零

库存。请比

O(nk)

或

O(n^2)

更高效地完成此操作。

O(n log k)

例如。

我可以在

O(nk)

中使用动态编程对我拥有的股票的日数和净数量来完成此操作。但我怎样才能更有效地做到这一点呢？

任何帮助将不胜感激。

谢谢！

Answer 1

您可以在 O(n log k) 时间内完成此操作。思考解决方案的方法有多种，但我认为最简单的方法是将其视为您已经了解的动态编程方法的优化。

假设您想要迭代这些日子，跟踪所持有的每种可能数量的股票的最佳现金头寸。我们会说 c_i 是您持有 i 股的最多现金。要以价格 p 计算新的一天，对于每个 i，您执行 c'_i = max( c_i-1-p, c_i+1+p, c_i )，找到最佳方法通过分别买入一支、卖出一支或持有来获得 i 股。

我们可以观察/证明这些现金头寸的一些有趣的特性：

1. 随着 i 的增加，c_i 单调减少——最终你会花费更多的钱来获得更多的股份。
2. 随着 i 的增加，差 c_i - c_i+1 增加。直观上，这是因为每个差异都是您可以购买/出售的某些股票的价格，并且首先购买最便宜的股票或先出售更昂贵的股票总是更好。形式上，我们可以归纳地证明它。我们称这种差异为 p_i
3. 当最好的 c_i 来自购买股票时，对于所有 c_{j > i} 也是如此。这很容易从(2)证明
4. 当最好的 c_i 来自出售股票时，对于所有 c_{j < i} 也是如此。这同样很容易从 (2) 证明

由于属性（2），我们不需要维护从每个 i 到 c 的映射。我们只需要维持一组差异，以及持有尽可能少的股份的最佳现金状况。

由于属性（3）和（4），我们需要对差异集进行的更改数量受常数限制。每天，您只需将 2 个 p 副本添加到差异集中，然后，如果差异超过 2k，则删除最高和最低的差异。

如果您以平衡 BST 或类似结构维护差异集，则这些添加和删除需要 log(k) 时间，从而导致总体算法为 O(n log k)。