标签 algorithm
<分区>
我在面试中被问到这个问题:
Best Time to Buy and Sell Stock
假设您有一个数组，其中第 i 个元素是给定股票在第 i 天的价格。 如果你只被允许买入一股股票和卖出一股股票，设计一个算法来找到最佳的买入和卖出时间。我能够给出 O(n) 算法。
面试官问了我一个followed on question，什么是“买一卖一”，然后又是“买一卖一”，也就是说一天有两笔交易，利润最大化。我能够给出一个 O(n^2) 算法。但是面试官说可以改进。是否有 O(n) 算法？
面试官说不能同时买两股。你必须买一个卖掉，然后在另一个时间买一个，然后卖掉。
最佳答案
原始问题的 reference 中给出的 O(n) 解为原始数组的每个前缀给出最佳的“买一个然后卖一个”答案。该算法也可以简单地修改以应对“向后”的情况；即“卖一个然后买一个”，你从数组向后工作；这相当于对数组的每个后缀都有“买一个然后卖一个”的答案。
现在，在“买，卖，买，卖”的情况下，我们有一些点(在第一次卖之后)我们在我们的数组中的某个地方，比如说 b。对于该断点，最佳解决方案是 0..b 的最佳前缀解决方案和 b+1..n 的最佳后缀解决方案。最好的“买、卖、买、卖”整体是这些最优解中的最优解。
因此，要在 O(n) 中解决“买，卖，买，卖”，您可以在 O(n) 中解决前缀，在 O(n) 中解决后缀O(n)，然后为每个断点计算最优值 - 所以 nO(1)。这是一个使用 O(n) 空间的 O(n) 算法。
关于algorithm - 一天内买卖股票，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9212299/