股票价格的最大利润

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)。

有人可以帮助我吗？谢谢

Answer 1

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

通过反向线性扫描很容易做到：

我们有 A = [4,6,2,1]，所以第一步我们取 A 的最后一个元素，它是 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 天之后的最大值。

Answer 2

你不想在这里分而治之。您可以在线性时间 (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，其中包含您的整数价格。

这里的关键是，你可以从最后开始，往回走，得到你需要的所有信息。

股票价格的最大利润

Max Profits of Stock Prices

arrays

algorithm

brute-force

time-complexity

divide-and-conquer