This is the 9th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

preface

Daily a JS algorithm, today to an array related algorithm, its name is called the best time to buy and sell stocks, when I see this topic WHEN I actually have that moment thought is the real stock… So let’s see what they’re doing

Topic describes

Given an array prices, its ith element prices[I] represents the price of a given stock on day I.

You can only buy the stock on one day and sell it on a different day in the future. Design an algorithm to calculate the maximum profit you can make.

Return the maximum profit you can make from the transaction. If you can’t make any profit, return 0.

 

Example 1:

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

Output: 5

Explanation: Buy on day 2 (stock price = 1), 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.Copy the code

Example 2:

Enter: prices = [7,6,4,3,1]

Output: 0

Explanation: In this case, no transaction is completed, so the maximum profit is 0.

Their thinking

  • The first thought of this question is to sort, but after carefully reading the requirements of the question, I found that can not be, because to ensure that the sale must be before the purchase
  • So let’s use a double for loop, let’s say I buy stocks every single day, and then I find the maximum on the second for loop, and I’ll code it
var maxProfit = function (prices) {
            let maxValue = 0
            let curr = prices[0]
            let median = 0
            for (let i = 0; i < prices.length - 1; i++) {
                curr = prices[i]
                for (let j = i + 1; j < prices.length; j++) {
                    if (prices[j] > curr && (prices[j] - curr > maxValue)) {
                        maxValue = prices[j] - curr
                    }
                }

            }
            if (maxValue > 0) {
                return maxValue
            } else {
                return 0}};Copy the code
  • As shown in the code above, run the for loop twice to get the maximum number of shares you buy each day and the maximum number of shares you sell on the following day. Then find the maximum value among all the maximum values to get the maximum profit, but because of the violent solution of the for loop, it times out…

  • We first declare two variables, maxProfit and minPrice. In the for loop, we compare each variable with minPrice. If it is smaller than minPrice, then we update minPrice. If it is greater than minPrice and the difference between this and minPrice is greater than maxProfit, then maxProfit is updated
  • To note here is the largest profit is zero, and a is the initial value of minPrice here I use is the maximum number of data in the array, the aim is to iterate through all the data, of course, you set minPrice to also can be a very big value, anyway, to set up the minimum to the maximum value of the data in an array, So here’s the code
var maxProfit = function(prices) { let maxProfit = 0 let minPrice = Math.max.apply(null,prices) for(let i=0; i<=prices.length-1; i++){ if(prices[i]<minPrice){ minPrice=prices[i] }else if(prices[i]-minPrice>maxProfit){ maxProfit = prices[i]-minPrice } } if(maxProfit>0){ return maxProfit }else{ return 0 } };Copy the code

conclusion

If we can’t think of dynamic programming, we can use the for loop to solve it. But dynamic programming can really improve our code, but the most important thing is the idea.