36 - 买卖股票的最佳时机

题目

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。

注意你不能在买入股票前卖出股票。

示例 1:

输入: [7,1,5,3,6,4] 输出: 5 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

示例 2:

输入: [7,6,4,3,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

解答

想法是：把某数之后的数字排序，然后相减。得到几个值，取最大值。

不过sort之后数组就改变了，似乎不行。

暴力法

也可以是从后往前，一个个数字找最小值；或是从前往后一个个找最大值。

var maxProfit = function (prices) {
  if (prices.length === 0) {
    return 0
  }
  const len = prices.length
  let max = 0
  for (let i = 0; i < len; i++) {
    for (let j = i; j < len; j++) {
      if (prices[i] < prices[j]) {
        let delta = prices[j] - prices[i]
        max = delta > max ? delta : max
      }
    }
  }
  return max
};

Runtime: 312 ms, faster than 19.40% of JavaScript online submissions for Best Time to Buy and Sell Stock.

Memory Usage: 35.4 MB, less than 81.97% of JavaScript online submissions for Best Time to Buy and Sell Stock.

显然两两比较能解决问题，不过太麻烦了。很多的数字都跑过了不止一遍

一次遍历

存一下当前最小值，和最大差值，到最后返回最大差值即可

var maxProfit = function (prices) {
  if (prices.length === 0) {
    return 0
  }
  let min = Number.MAX_SAFE_INTEGER
  let max_delta = 0
  for (const item of prices) {
    min = item < min ? item : min
    max_delta = (item - min) > max_delta ? (item - min) : max_delta
  }
  return max_delta
};

Runtime: 52 ms, faster than 95.82% of JavaScript online submissions for Best Time to Buy and Sell Stock.

Memory Usage: 36.8 MB, less than 9.57% of JavaScript online submissions for Best Time to Buy and Sell Stock.

可能是最大安全数比较占内存。第一个数换成prices的第一个元素，就会更加平衡一些

...
  let min = prices[0]
...

Runtime: 64 ms, faster than 57.81% of JavaScript online submissions for Best Time to Buy and Sell Stock.

Memory Usage: 36.6 MB, less than 14.48% of JavaScript online submissions for Best Time to Buy and Sell Stock.

最大连续子数组和

区间和与求差问题，是等价的。

$dp[i]$ 表示以i为结尾的最大连续子数组和，递推公式为：

$$dp[i] = max(0, dp[i-1])$$

作者：ivan_allen

链接：https://leetcode-cn.com/problems/two-sum/solution/121-mai-mai-gu-piao-de-zui-jia-shi-ji-dp-7-xing-ji/

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

Runtime: 56 ms, faster than 87.70% of JavaScript online submissions for Best Time to Buy and Sell Stock.

Memory Usage: 35.5 MB, less than 61.04% of JavaScript online submissions for Best Time to Buy and Sell Stock.

last记录循环累计的差值，把最大差值记录在profit里面。

go

用go写了一个版本：

func maxProfit(prices []int) int {
    if len(prices) == 0 {
        return 0
    }
    min := math.MaxInt64
    max_delta := 0
    for _, elem := range prices {
        if elem < min {
            min = elem
        }
        if (elem - min) > max_delta {
            max_delta = elem - min
        }
        runtime.Gosched()
    }
    return max_delta
}

Runtime: 4 ms, faster than 97.10% of Go online submissions for Best Time to Buy and Sell Stock.

Memory Usage: 3.1 MB, less than 100.00% of Go online submissions for Best Time to Buy and Sell Stock.