股票价格的最大利润

Question

我正在尝试设计一个O(nlogn)时间的分治算法来解决以下现实问题 -

假设我们有一组股票价格的数组。提供一个算法，输出一个包含每个i天最大利润的数组。

例如，如果我们有数组A=[4,6,2,1]，则我们的天数表示每个索引，我们的输出将是一个值为[2,-4,-1,-1]的数组，其中最后一天的值为-A[i]。

我已经设计出了一个暴力算法-

   1.) Scans the array for max after A[i]
   2.) Subtracts A[i] with max, places value in A', iterates to next day
   3.) When max reaches itself, repeat steps 1 & 2
   4.) When you reach the end, the value is -A[i], return

此外，我不确定上述算法的时间复杂度是O(n)还是O(n^2)。在该算法中，最大的花费在于查找最大值，其他所有操作都是O(1)。

有人能帮忙解答吗？谢谢！

- user4309564

---

你可以在线性时间内完成这个任务。尝试在数组上进行一次反向遍历，以获取所需的所有信息。 - user2357112

我不明白，从最后开始，不断减去值以找到每个特定日期的最大利润？ - user4309564

Answer 1

您不希望在此使用分治算法。您可以在线性时间（O(n)）内完成此操作。以下是Java代码，但您可以使用任何语言：

int[] maxProfit = new int[prices.length];
int maxPrice = 0;
for (int i = prices.length - 1; i >= 0; i--) {
 maxProfit[i] = maxPrice - prices[i];
 maxPrice = Math.max(maxPrice, prices[i]);
}

假设您有一个包含整数价格的数组prices。

关键在于您可以从末尾开始向后遍历，以获取所需的所有信息。

- nhouser9

---

啊，我明白了。由于只需一次遍历数组，时间复杂度将是简单的O(n)。然而，我仍在分析这个简单问题的不同时间复杂度，并且对于O(logn)感到困惑。我知道它不如这个算法高效。但是，我对如何在每种不同的分割数组和插入数组的情况下找到最佳方法感到困惑。 - user4309564

@tarfar 在这里，分治解决方案并不适用。事实是，对于每个元素，我们都必须查看它之后的每个元素。因此，即使我们以某种方式“分割”数组，我们仍然必须查看其他部分来确定结果。 - nhouser9

是的，我明白，只是好奇它是如何工作的。O(n)算法非常快，但是我正在分析分治算法，并将其应用于不同的问题以更好地理解概念。因此，当我们划分每一半时，我们需要将其与另一半进行比较吗？ - user4309564

Answer 2

这可以在一次线性扫描中完成，因此复杂度为O(n)。首先让我们创建最大数组M，即M[i]包含第i天之后我们拥有的最大数字。

通过反向线性扫描很容易实现：

假设我们有A = [4,6,2,1]，那么首先我们取最后一个元素1作为当前最大值，即M[3] = 1，然后我们计算M[2] = max(M[3],A[2]) = 2，接着我们计算M[1] = max(M[2],A[1]) = 6，最后一步计算得到M[0] = max(M[1], A[0]) = 6。

我们将有M = [6,6,2,1]。该算法具有O(n)的复杂度，然后我们将运行一个循环来识别每天的最大利润，这也具有O(n)的复杂度。顺便说一下，我们可以省略存储M值的步骤，而是只存储第i天后的最大值。

- simon

---

@tarfar 对于造成的混淆表示抱歉，M[i] 是一个子数组 A[i], A[i+1], ..., A[A.length-1] 中的最大值。在这种情况下，最大收益 P 将等于 P[i] = M[i+1]-A[i]，因此 P=[6-4, 2-6, 1-2, 0-1] = [2, -4, -1 ,-1]。 - simon

O(n)比O(nlogn)更快，但是让我们使用分治法。假设我们已经解决了AL=[4,6]和AR=[2,1]的问题。解决方案为SL=[2,-6]和SR=[-1,-1]。我们必须连接SL和SR以获得A=[4,6,2,1]问题的答案。为此，我们不会触及AR中的任何内容，只需考虑AL[i]项后面的最大数字和AR数组的最大数字即可。因此，对于AL[0]，我们将得到最大值为6，它在AL中，因此我们不会触及它；对于AL[1]，最大值为2，它在AR数组中，我们必须进行调整，我们将得到SL_adjusted[1]=-6+2=-4。=> S=[2,-4,-1,-1] - simon

@tarfar，这不是使用分治技术的好问题。如果你想学习和练习这种方法，归并排序是最好的案例，可以说明这种方法。 - simon

关于时间复杂度：使用主定理证明分治法的复杂度为O(nlogn)更好。正如您所看到的，我们将数组分成两个相等的数组，然后进行线性工作以组合结果，因此T(n) = 2T(n/2)+cn。从主定理中，我们将得到T(n) = O(nlogn)。 - simon

哇，你太有帮助了！非常感谢你！在你的帮助下，我绝对更好地理解了这个问题。 - user4309564