arrays - 股票价格的最大利润

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)) 内执行此操作。这是 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，其中包含您的整数价格。

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