The title

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

Design an algorithm to calculate the maximum profit you can make. You can make up to two deals.

Note: You can’t participate in more than one transaction at a time (you must sell your previous shares before buying again).

Example:

Input: prices = [3,3,5,0,0,3,1,4] Output: 6 Explanation: If you buy on day 4 (stock price = 0) and sell on day 6 (stock price = 3), this transaction will make a profit = 3-0 = 3. Then, by buying on day 7 (stock price = 1) and selling on day 8 (stock price = 4), the exchange makes a profit of 4-1 = 3.Copy the code

Example 2:

Explanation: If you buy on day 1 (stock price = 1) and sell on day 5 (stock price = 5), this transaction will make a profit = 5-1 = 4. Note that you can't buy stocks on day 1 and day 2 and then sell them later. Because you're doing multiple trades at once, you have to sell your shares before you can buy them again.Copy the code

Example 3:

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

Example 4:

Input: prices = [1] Output: 0Copy the code

The collapse of the train of thought

In calculating returns, we first maintain four parameters, namely, first buy, first sell. Buy the second time, sell the second time. Here, if we need to buy and sell twice, we should subtract the profit of the first time at the time of the second purchase, so that we can not consider the profit of the first purchase to maintain, at the time of the second purchase we will have a lower price, calculated into the cost price.

Complex concepts here we do not need tedious text description, to use the code to explain, look at my notes yo, follow my ideas

/** * @param {number[]} prices * @return {number} */ var maxProfit = function(prices) {/** First purchase price fstSell: the price at which you can gain the most from the first purchase (secSell > fstSell) */ let fstBuy = math.pow (2,53); // let fstSell = 0; // let secBuy = math.pow (2,53); // let secSell = 0; // for(const p of prices){fstBuy = math.min (fstBuy, p); Max (fstSell, p-fstbuy) = math. Max (fstSell, p-fstbuy); fstSell = math. Max (fstSell, p-fstbuy); SecBuy = Math. Min (secBuy, p-fstsell); secBuy = Math. // Sell the second time, again, compare sell or hold, find the maximum sell, sell, get the maximum profit. secSell = Math.max(secSell, p - secBuy); } return secSell; };Copy the code

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