【算法】买卖股票的最佳时机-动态规划

题目

原题地址：121. 买卖股票的最佳时机 - 力扣（LeetCode）

解题思路

需要在一次交易中获取最大利益，也就是求数组元素的最大差值。此外，第二个数字（卖出价格）必须大于第一个数字（买入价格）。

第 i 天能获取的最大利润是第 i 天的价格减去之前天数中价格的最小值。

根据这个思路，可以实现以下算法：

var maxProfit = function (prices) {
  let profit = 0;
  let min = prices[0];
  for (let i = 1; i < prices.length; i++) {
    min = Math.min(prices[i], min);
    profit = Math.max(profit, prices[i] - min);
  }

  return profit;
};

• 时间复杂度：O(n)，只需要遍历一次，n 为数组的长度。
• 空间复杂度：O(1)，只使用了常数个变量。