The topic of dry

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: [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.Copy the code

Idea 1: Violence (timeout)

Loop over and judge

let profit = 0;
    let length = prices.length
    for (let index = 0; index < length; index++) {
        let beginDay = prices[index]
        for (let indey = index + 1; indey < length; indey++) {
            let tempprofit = prices[indey] - beginDay
            if (tempprofit > profit) {
                profit = tempprofit
            }
        }
    }
    return profit
Copy the code

Idea 2: Greed

We set a minimum price and a current profit, and then loop once, encountering a value less than the current minimum price, replacing the minimum price. If the profit in the current cycle is greater than the current profit, replace the current profit so that the minimum input point can be found and the highest throw point can be calculated

Execution time: 124 ms, beating 38.04% of all JavaScript commits

Memory consumption: 47.6 MB, beating 66.07% of all JavaScript commits

 var maxProfit = function (prices) {
    let minprice = prices[0];
    let profit = 0;
    for (let i = 0; i < prices.length; i++) {
      if (minprice > prices[i]) {
        minprice = prices[i]
      } else if (prices[i] - minprice > profit) {
        profit = prices[i] - minprice
      }
    }
    return profit
Copy the code