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

  • So you can only compare backwards

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

The sample

Input:7.1.5.3.6.4] output:5Explanation: If the first day buy for7Every day after that7Small, if how can compensate be bought the next day1 ，1The following numbers are in order with1The comparison,6 - 1 = 5The results obtained are maximum if bought on the third day5, followed only by6Sell it, you get it1The maximum...Copy the code

Their thinking

  • In order to,1,5,3,6,4 [7]As an example
  • Since existence buys and sells, that is the hope buys in nadir certainly, the highest point sells
  • So we use a variable to record the lowest price everminPriceAnd then let’s say I’m at number oneiIf I sell it in the first day, my profit will beprices[i] - minprice
  • Then we loop through the array, recording the lowest price, and each time we compare how much we can make if we sell today
  • When the loop ends, you have your answer

code

var maxProfit = function (prices) {
  // Assume that the first day is the lowest
  let minprice = prices[0],
    maxprofit = 0;
  // We can't sell from 0 because we bought on the first day
  for (let i = 1; i < prices.length; i++) {
    // If there is a minimum substitution
    if (prices[i] < minprice) {
      minprice = prices[i];
    } else {
      // Calculate how much money you can make by selling today
      let profit = prices[i] - minprice;
      // Select a larger value from the previous calculation
      maxprofit = Math.max(maxprofit, profit); }}return maxprofit;
};


Copy the code