这个问题（最后一个）出现在 Benelux Algorithm Programming Contest-2007
http://www.cs.duke.edu/courses/cps149s/spring08/problems/bapc07/allprobs.pdf
公司需要确定何时在给定输入上购买或出售或无操作的策略，以实现利润最大化。输入格式为：
6
4 4 2
2 9 3
....
....
这意味着输入的时间为 6 天。
第 1 天：您获得 4 股，每股价格为 4 美元，最高可以卖出 2
股 第 2 天：您获得 2 股，每股价格为 9 美元，最高可以卖出 3 股
。
我们需要输出可以达到的最大利润。
我正在考虑如何解决这个问题。在我看来，如果我们使用蛮力，将花费太多时间。如果这可以转换为像 0-1 背包这样的 DP 问题？一些帮助将不胜感激。
我们不能比在当天以最高价格卖出最大数量的股票做得更好，所以我在想：（这可能有点难以（有效地）实施）
计算到目前为止每天收到的股票总数以提高算法的效率可能是一个好主意。
按价格降序处理天数。
一天，sell amount = min(daily sell limit, shares available)（对于最高价格日（第一个处理日），可用股票 = 迄今为止收到的股票）。
在随后的所有日子里，shares available -= sell amount. 对于前几天，我们二分查找(shares available - shares sold)该日与刚刚处理的那一天之间的所有条目 = 0。
我们可能不需要物理设置值（至少不需要在每一步），只需从迄今为止的历史中即时计算它们（我在考虑区间树或类似的东西）。
您的描述与 PDF 中的最后一个问题不完全匹配 - 在 PDF 中，您收到第一列中指定的股票数量（或被迫购买它们 - 因为没有决定做出无关紧要）并且只能决定卖出多少股。因为它没有另外说明，所以我认为卖空是不允许的（否则忽略除价格之外的一切，并在衍生品市场上赚到这么多钱，以至于你既可以贿赂 SEC 或国会，又可以退休:-)）。
这看起来像一个动态程序，其中每个时间点的状态是您手头的股份总数。因此，在时间 n 时，您有一个数组，其中每个可能的股票数量都有一个元素，您当时可能最终获得的股票数量，并且在该元素中，您拥有到那时您可以赚到的最大金额，同时以该数字结束的股份。由此您可以计算出时间 n+1 的相同信息。当你到达终点时，你所有的股票都一文不值，所以最好的答案是与最大金额相关的股票。
可以通过DP解决
假设有n天，股票总数为m
设 f[i][j] 表示在第 i 天，剩余 j 股，最大利润为 f[i][j]
显然，f[i][j]=maximum(f[i-1][j+k]+k*price_per_day[i]), 0<=k<=maximum_shares_sell_per_day[i]
可以进一步优化，因为 f[i][...] 只依赖于 f[i-1][...]，所以这里可以使用滚动数组。因此你只需要定义 f[2][m] 来节省空间。
总时间复杂度为 O(n*m*maximum_shares_sell_per_day)。
也许可以进一步优化以节省时间。欢迎任何反馈