“This is the 30th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

122. The best time to Buy and sell stocks II

The title

You are given an array prices, where prices[I] represents the price of the stock on day I.

On each day, you may decide to buy and/or sell shares. You can’t hold more than one share at any time. You can also buy it and sell it on the same day. Return the maximum profit you can make.

Example 1

Input: prices = [7,1,5,3,6,4] Output: 7 Then, by buying on day 4 (stock price = 3) and selling on day 5 (stock price = 6), the exchange makes a profit = 6-3 = 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

Answer key

greedy

Assuming that the stock price as the array of time is: prices =,1,5,3,6,4 [7] prices =,1,5,3,6,4 [7] prices =,1,5,3,6,4 [7];

Prices [I]>prices[I −1]prices[I]prices[I]>prices[I −1] Prices [I]prices[I]>prices[I −1] Prices [I]prices[I]>prices[I −1] Prices [I]prices[I]prices[I]prices[I]prices[I]prices[I]prices[I]prices[I]prices[I]prices[I]prices[I]prices[I]prices[I]prices[I]prices[I]prices[I]prices[I]prices[I]prices[I]prices[I]prices[I]prices[I −1]

Accruing each benefit yields the entire array benefit

Stock prices, days and earnings statements

I day 1 2 3 4 5 6
The price 1 5 3 6 4
I – 1 day price 7 1 5 3 6 4
result 0 4 0 3 0 0

result = 7

Edit the code as follows:

var maxProfit = function(prices) {
    const len = prices.length;
    if(len === 1) return 0;
    let result = 0;
    for(let i = 1 ; i < len ; i++){
        if(prices[i] > prices[i-1]){
            result+=  (prices[i] - prices[i-1])}}return result

};
Copy the code

Dynamic programming

There are only two possibilities for analyzing day III:

  • Using two-dimensional array dp [I] [0], dp [I] [1] dp [I] [0], dp [I] [1] dp [I] [0], dp [I] [1] said the two states
  • Dp [I][0] DP [I][0] DP [I][0] no shares on day III
  • Dp [I][1] DP [I][1]dp[I][1] indicates there are shares on day III

There are also two possibilities for day iii gains:

  • On day I, there’s no stock, so maybe I sold the stock on day I minus day 1, or MAYBE I didn’t buy the stock on day I
  • I have a stock on day I, it could be a stock on day I minus day 1, it could be a stock that I just bought on day I,

So day I has no state transition equation for stocks: Dp [I] [0] = math.h Max (dp [0], [I – 1] dp [I – 1) + prices [1] [I]) dp [I] [0] = math.h Max (dp [0], [I – 1] Dp] [I – 1 + prices [1] [I]) dp [I] [0] = math.h Max (dp [0], [I – 1] dp [I – 1] [1] + prices [I])

Day I has the state transition equation of the stock: Dp [I] [1] = math.h Max (dp [1], [I – 1] dp [I – 1] [0] – prices [I]) dp [I] [1] = math.h Max (dp [1], [I – 1] Dp [0] – [I – 1] prices [I]) dp [I] [1] = math.h Max (dp [1], [I – 1] dp [I – 1] [0] – prices [I])

Edit the code as follows:


var maxProfit = function (prices) {
  // Dynamic programming
  const len = prices.length;
  const dp = [];
  for (let i = 0; i <= len; i++) {
    dp[i] = [];
  }
  dp[0] [0] = 0;
  dp[0] [1] = -prices[0];
  // 0 there is no stock on that day,
  // 1 There are stocks on that day
  let result = 0;
  for (let i = 1; i < len; i++) {
    // No stock, no stock the day before, no stock the day before, sold today
    dp[i][0] = Math.max(dp[i - 1] [0], dp[i - 1] [1] + prices[i]);
    dp[i][1] = Math.max(dp[i - 1] [1], dp[i - 1] [0] - prices[i]);
    result = Math.max(dp[i][0], dp[i][1]);
  }
  return result;
};
Copy the code