分治排序算法

Question

这就像一个股票营销的问题，我困惑的是，问题是如何获得每天的最大利润？我只知道算法的时间复杂度可以是O(n)或O(n log2 n)。

输入是A，一组股票价格。对于第一天来说，最好的交易是通过在第一天买进，然后在随后的一天卖出，从而获得最大的利润。为了方便起见，您可以将最后一天的最佳交易定义为n−A。给出一个算法的伪码，该算法返回一个数组，其中包含A中每天的最大利润。

更新:我现在知道如何获得最大利润，我可以使用类似的算法，如合并排序，分而治之，以找到这个最大的利润。我的问题是，用时间复杂度O(n)寻找最大利润的另一种方法(算法)是什么，或者我如何以这种方式进行处理？

Answer 1

考虑到这个问题的一种方法是使用一个for循环，因为它是O(n)，我可以给您一些提示：

    for i from 0 to n:
        if (A[i] < A[min])   // find the minimum value of stock
          min = i;
        profit = A[i] - A[min]    // get the profit
        if (profit > maxProfit) {   // compares the profits
          maxProfit = profit   // always update the max profit

Answer 2

如果你在第一天买i，你能赚到的最大利润是Amax(i) - A[i]，其中Amax(i)是第二天i之后的最高价格。我对算法规范的理解是，您要构造并返回数组M，其条目由M[i] = Amax(i) - A[i]定义。

第二天i之后的最高价格是A[i+i]的最高价格和第二天的i + 1之后的最高价格。

最后一段给出了一个递归关系，但与您可能看到的“典型”递归不同，ith值依赖于i + 1st值，而不是相反。但是对您来说幸运的是，您已经知道nth值和以后的每一个值都是0，也就是说，在n之后，您的股票将得到0。因此，您只需要计算天1，2，.，n - 1的值，这可以在O(n)时间内完成。每次您找到这些值之一Amax(i)时，您都可以使用M[i] = Amax(i) - A[i]设置M的一个条目。

如果您想要通过在任何一天购买一股股票并在随后的任何一天卖出而获得最大利润(虽然问题声明并不需要这样做，但据我所见)，您只需在M中找到最大值，这可以在O(n)时间内完成。

如果你的目标是通过一系列买卖股票的行为使利润最大化，那么你所能做的最好的就是在股票在当地最低时(在第一天之前假定无限价格)买尽可能多的股票，并在达到当地最高价格时出售所有的东西。您可以识别O(n)时间内的所有局部极小和最大值，向任意方向扫描A，并且给定起始金额，可以使用局部极小和A的最大值列表计算O(n)时间内的最大总利润。(但这并不使用原始问题语句要求您构造的数组，因为该数组没有考虑购买股票的数量，也没有考虑多个事务的可能性。)

请记住，如果两次传递算法的每次传递都需要O(n)时间，则整个算法都需要O(n)时间。