最佳买卖股票时间
任务描述
假设有一个数组 prices，其中第 i 个元素是股票在第 i 天的价格。
找出最大利润。你可以进行任意次数的交易（即，买一次并卖出一次股票多次）。
注意：你不能同时进行多次交易（即，在再次购买股票之前必须先卖出股票）。
示例 #1
输入: [7, 1, 5, 3, 6, 4]
输出: 7
解释：在第 2 天买入（价格 1）并在第 3 天卖出（价格 5），利润为 5-1=4。然后在第 4 天买入（价格 3）并在第 5 天卖出（价格 6），利润为 6-3=3。
示例 #2
输入: [1, 2, 3, 4, 5]
输出: 4
解释：在第 1 天买入（价格 1）并在第 5 天卖出（价格 5），利润为 5-1=4。注意，你不能在第 1 天买入，然后在第 2 天买入然后卖出它们，因为你在同一时间进行了多次交易。你必须先卖出再买入。
示例 #3
输入: [7, 6, 4, 3, 1]
输出: 0
解释：在这种情况下，没有进行任何交易，即最大利润为 0。
可能的解决方案
分治法 O(2^n)
我们可以尝试所有可能的买卖组合，并通过应用 分治法 找出最有利可图的一种。
假设我们有价格数组 [7, 6, 4, 3, 1]，我们正处于第 1 天的交易中（在数组的开始）。此时，我们可以说整体最大利润将是以下两个值的 最大值：
- 选项 1: 留住这笔钱 → 利润将等于从购买/卖出剩余股票中获得的利润 →
keepProfit = profit([6, 4, 3, 1])。 - 选项 2: 在当前价格时买入/卖出 → 在这种情况下，利润将等于从购买/卖出剩余股票中获得利润加上（或减去，取决于我们是卖出还是买入）当前股票价格 →
buySellProfit = -7 + profit([6, 4, 3, 1])。
整体利润将等于 → overallProfit = Max(keepProfit, buySellProfit)。
正如您所看到的，profit([6, 4, 3, 1]) 任务以相同的递归方式解决。
见完整代码示例在 dqBestTimeToBuySellStocks.js
时间复杂度
如您所见，每个递归调用都会产生 2 个更多的递归分支。递归的深度将是 n（价格数组的大小），因此时间复杂度将等于 O(2^n)。
如您所见，这非常低效。例如，对于仅仅 20 个价格，递归调用的数量将在 2M 左右！
额外空间复杂度
如果我们避免在递归函数调用之间克隆价格数组，并将指针用于数组，则额外空间复杂度将与递归深度成正比：O(n)
峰谷法 O(n)
如果我们绘制价格数组（即 [7, 1, 5, 3, 6, 4]），我们可以注意到感兴趣的点是连续的谷底和峰值
图像来源：LeetCode
因此，如果我们将在价格上升时跟踪增长，并且在价格下降之前立即卖出股票，我们将获得最大利润（记住，我们在谷底以低价购买了股票）。
见完整代码示例在 peakvalleyBestTimeToBuySellStocks.js
时间复杂度
由于该算法只需遍历价格数组一次，时间复杂度将等于 O(n)。
额外空间复杂度
除了价格数组本身之外，该算法消耗常数量的内存。因此，额外空间复杂度为 O(1)。
累加器法 O(n)
甚至存在更简单的解决方案。假设我们有这样的价格数组 [1, 7, 2, 3, 6, 7, 6, 7]：
图像来源：LeetCode
您可能会注意到，我们甚至不需要跟踪不断增长的房价。相反，我们可以简单地添加图表中所有增长段的房价差，最终总和为可能的最大利润，
时间复杂度
由于该算法只需遍历价格数组一次，时间复杂度将等于 O(n)。
额外空间复杂度
除了价格数组本身之外，该算法消耗常数量的内存。因此，额外空间复杂度为 O(1)。