解决方案

我们需要找出给定数组中两个数字之间的最大差值(即,最大利润)。此外,第二个数字(卖出价格)必须大于第一个数字(买入价格)。

形式上,对于每组 (其中 )我们需要找出


方法一:暴力法

复杂度分析

  • 时间复杂度:。循环运行 次。

  • 空间复杂度:。只使用了两个变量 ——


方法二:一次遍历

算法

假设给定的数组为:

[7, 1, 5, 3, 6, 4]

如果我们在图表上绘制给定数组中的数字,我们将会得到:

Profit Graph

使我们感兴趣的点是上图中的峰和谷。我们需要找到最小的谷之后的最大的峰。 我们可以维持两个变量——minprice 和 maxprofit,它们分别对应迄今为止所得到的最小的谷值和最大的利润(卖出价格与最低价格之间的最大差值)。

复杂度分析

  • 时间复杂度:。只需要遍历一次。

  • 空间复杂度:。只使用了两个变量。