Leetcode 0123. the best time to buy and sell stocks III: dynamic programming + simulation in constant space

【LetMeFly】123. The best time to buy and sell stocks III： Dynamic programming in constant space + simulation

Force button topic link ：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/

Given an array , It's the first i An element is a given stock in the i Sky price .

Design an algorithm to calculate the maximum profit you can get . You can do at most   Two pens   transaction .

Be careful ： You can't participate in multiple transactions at the same time （ You have to sell the stock before you buy it again ）.

 

Example  1:

 Input ：prices = [3,3,5,0,0,3,1,4]
 Output ：6
 explain ： In the  4  God （ Stock price  = 0） Buy when , In the  6  God （ Stock price  = 3） Sell when , The exchange will make a profit  = 3-0 = 3 .
      And then , In the  7  God （ Stock price  = 1） Buy when , In the  8  God  （ Stock price  = 4） Sell when , The exchange will make a profit  = 4-1 = 3 .

Example 2：

 Input ：prices = [1,2,3,4,5]
 Output ：4
 explain ： In the  1  God （ Stock price  = 1） Buy when , In the  5  God  （ Stock price  = 5） Sell when ,  The exchange will make a profit  = 5-1 = 4 .   
      Notice that you can't be in the  1  Day and day  2  Day after day buying stock , Then sell them .   
      Because it's involved in multiple transactions at the same time , You have to sell the stock before you buy it again .

Example 3：

 Input ：prices = [7,6,4,3,1] 
 Output ：0 
 explain ： In this case ,  No deal is done ,  So the biggest profit is  0.

Example 4：

 Input ：prices = [1]
 Output ：0

 

Tips ：

• 1 <= prices.length <= 105
• 0 <= prices[i] <= 105

Method 1 ： Dynamic programming in constant space

This question, frankly speaking, has at most $5$ Status ：

• There has been no transaction
• Made a purchase
• Made a deal
• Made a deal + One time purchase
• Two transactions

When there is no transaction , The profit is $0$, Therefore, there is no need to pay special attention .

Use four variables $buy1,sell1,buy2,sell2$ When the transaction reaches the remaining four states , The current maximum profit .（ Here, try to match the variable name with Official explanation bring into correspondence with ）

Next, we strictly abide by the meaning of the above four variables

Assign the initial values of the four variables to the maximum profit value after the first day ：

• $buy1$： On the first day, I made a purchase . Then the current maximum profit is $Negative\; first\; day\; share\; price$（ It's the biggest profit , In fact, the first day of this state, there is no choice , There is only one profitable result ）
• $sell1$： On the first day, a deal was made . Then the buying and selling prices are the same , The current maximum profit is $0$
• $buy2$： On the first day, a deal was made + One time purchase . That is to say, I bought it once on the first day and sold it immediately , Then I bought it again , total ( Maximum ) Profit for $Negative\; first\; day\; share\; price$
• $sell2$： On the first day, there were two transactions . The total revenue is $0$

int buy1 = -prices[0]
int sell1 = 0;
int buy2 = -prices[0]
int sell2 = 0;

Next , From $2$ Day begins , Before simulation $i$ God , The maximum profit in each state .

• $buy1$： front $i$ The maximum profit of buying only once a day .$buy=\max (bu{y}^{\prime },-prices[i])$. in other words , It can be before $i-1$ Make a purchase when the stock price is low ($bu{y}^{\prime }$), You can also not be in front $i-1$ I bought it on the day $i$ Sky buying ($-prices[i]$).（ Here we use $bu{y}^{\prime }$ On behalf of the $i-1$ days $buy$ Value ）
• $sell1$： front $i$ Once a day .$sell1=\max (sell{1}^{\prime },buy{1}^{\prime }+prices[i])$. in other words , It can be in front $i-1$ I bought and sold once a day and didn't do anything today ($sell{1}^{\prime }$), It can also be the former $i-1$ I only bought on the day and on the $i$ Day sell ($buy{1}^{\prime }+prices[i]$)（ Selling will make a profit $prices[i]$）
• $buy2$： front $i$ Once a day + One time purchase .$buy2=\max (buy{2}^{\prime },sell{1}^{\prime }-prices[i])$. in other words , It can be in front $i-1$ A deal was made on the day + Buy once and do nothing today ($buy{2}^{\prime }$), It can also be the former $i-1$ A sale was made on the day and on the $i$ Day bought again ($sell{1}^{\prime }+(-prices[i])$)（ Buying will cost $prices[i]$）
• $sell2$： front $i$ Two transactions have been made in the past few days .$sell2=\max (sell{2}^{\prime },buy{2}^{\prime }+prices[i])$. It can be in front $i-1$ I bought and sold twice a day and didn't do anything today ($sell{2}^{\prime }$), It can also be the former $i-1$ There was only one deal in the past day + Buy once and in the $i$ Tian sold and bought for the second time ($buy{2}^{\prime }+prices[i]$)（ Selling will make a profit $prices[i]$）

therefore , Simulation finished $n$ Days later , return $sell2$ that will do （ Two transactions ）

Be careful , In the title, there are two transactions at most , That is to say, you can only do one transaction or no transaction . Selling on the same day without buying or selling is equivalent , Therefore, it can be understood that you must buy and sell twice, but you may have sold on the same day you bought .

• Time complexity $O(n)$
• Spatial complexity $O(1)$, Only constant extra space is used

AC Code

C++

class Solution {
    
public:
    int maxProfit(vector<int>& prices) {
    
        int buy1 = -prices[0], sell1 = 0;
        int buy2 = -prices[0], sell2 = 0;
        for (int i = 1; i < prices.size(); i++) {
    
            buy1 = max(buy1, 0 + (-prices[i]));
            sell1 = max(sell1, buy1 + (prices[i]));
            buy2 = max(buy2, sell1 + (-prices[i]));
            sell2 = max(sell2, buy2 + (prices[i]));
        }
        return sell2;
    }
};

The code is very short , The key is to strictly follow the definition of variables and understand .

Synchronous posting on CSDN, Originality is not easy. , Reprint please attach Link to the original text Oh ~
Tisfy：https://letmefly.blog.csdn.net/article/details/125889831