Title: The best time to buy and sell stocks

Subject address: leetcode-cn.com/problems/be…

Given an array, its ith element is the price of a given stock on the ith day.

If you only allow one trade (buy and sell a stock once), design an algorithm to calculate the maximum profit you can make.

Note: You cannot sell a stock before you buy it.

Example 1:

Input: [7,1,5,3,6,4] output: 5 explanation: buy on day 2 (stock price = 1) and sell on day 5 (stock price = 6), maximum profit = 6-1 = 5. Note that the profit cannot be 7-1 = 6, because the selling price needs to be higher than the buying price; Also, you can’t sell stocks before you buy them. Example 2:

Input: [7,6,4,3,1] output: 0 explanation: in this case, no transaction is completed, so the maximum profit is 0.

solution

1. The violence

  • The brute force solution is to start buying on the first day and record the maximum number of selling results on all subsequent days; Day 2, day 3… On the NTH day, I bought the maximum amount I sold on the last day
/ * * *@param {number[]} prices
 * @return {number}* /
var maxProfit = function (prices) {
  if(! prices || ! prices.length)return 0
  const len = prices.length
  let max = 0,
    cur = 0,
    next = 0
  for (let i = 0; i < len; i++) {
    cur = prices[i]
    for (let j = i + 1; j < len; j++) {
      next = prices[j]
      if (cur < next) {
        max = Math.max(max, next - cur)
      }
    }
  }
  return max
}
Copy the code

2. Lowest price recursion method

  • Since you buy before you sell, you only need to track the minimum and maximum differences as you move backwards
/ * * *@param {number[]} prices
 * @return {number}* /
var maxProfit1 = function (prices) {
  if(! prices || ! prices.length)return 0
  let min = prices[0] / / the minimum
  let res = 0 // Maximum difference
  for (let i = 0; i < prices.length; i++) {
    min = Math.min(min, prices[i])
    res = Math.max(res, prices[i] - min)
  }
  return res
}
Copy the code

Combine the code to view the basic principle:

How can we ensure that this way of thinking works?

  • Limit case: a smaller min value appears later

According to the calculation, even if the min value is smaller later, the highest profit can still be guaranteed to buy on the second day and sell on the third day, because Max is retained in a single cycle

The test case


// Test case
let test = [7.1.5.3.6.4]
let test1 = [7.6.4.3.1]

console.time("Execution time")
console.log(maxProfit(test))
console.log(maxProfit(test1))
console.log(maxProfit1(test))
console.log(maxProfit1(test1))
console.timeEnd("Execution time")
Copy the code

conclusion

  • In a single loop, track the minimum and maximum difference

instructions

  1. The GitHub address has been synchronized and the code can be copied for debugging.
  2. Summarized a set of effective front-end painless brush problem project, which can help algorithm white smooth start, see Leetcode-js-roadmap, hope to help front-end partners brush problem from scratch

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign