买卖股票的最佳时机 IV - 困难

*************
C++

topic：188. 买卖股票的最佳时机 IV - 力扣（LeetCode）

*************

Stock angin:

Still stocks. Intuitively, it feels hard. 

For once:

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        
        int minPrice = prices[0]; // 迄今为止遇到的最低价格
        int maxPro = 0; // 最大利润
        
        for (int i = 1; i < prices.size(); ++i) {
            // 如果当前价格比迄今为止的最低价格还低，更新最低价格
            if (prices[i] < minPrice) {
                minPrice = prices[i];
            } else {
                // 如果当前价格比最低价格高，计算利润，并更新最大利润
                maxPro = max(maxPro, prices[i] - minPrice);
            }
        }
        
        return maxPro;
    }
};

For twice.

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        
        int n = prices.size(); // get the length
 
        int firstBuy = - prices[0];
        int firstSale = 0;
        int secondBuy = - prices[0];
        int secondSale = 0;
 
        // do sth. here
        for (int i = 1; i < n; i++){
            firstBuy = max(firstBuy, - prices[i]);
            firstSale = max(firstSale, prices[i] + firstBuy);
 
            // the second sale
            secondBuy = max(secondBuy, firstSale - prices[i]);
            secondSale = max(secondSale, prices[i] + secondBuy);
        }
 
        return secondSale;
    }
};

For three times:
 

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.empty()) return 0;
 
        int n = prices.size();
        // 初始化状态变量
        int firstBuy = -prices[0];  // 第一次买入的最大利润
        int firstSell = 0;          // 第一次卖出的最大利润
        int secondBuy = -prices[0]; // 第二次买入的最大利润
        int secondSell = 0;         // 第二次卖出的最大利润
        int thirdBuy = -prices[0];  // 第三次买入的最大利润
        int thirdSell = 0;          // 第三次卖出的最大利润
 
        for (int i = 1; i < n; ++i) {
            // 更新第一次买入的最大利润
            firstBuy = max(firstBuy, -prices[i]);
            // 更新第一次卖出的最大利润
            firstSell = max(firstSell, firstBuy + prices[i]);
            // 更新第二次买入的最大利润
            secondBuy = max(secondBuy, firstSell - prices[i]);
            // 更新第二次卖出的最大利润
            secondSell = max(secondSell, secondBuy + prices[i]);
            // 更新第三次买入的最大利润
            thirdBuy = max(thirdBuy, secondSell - prices[i]);
            // 更新第三次卖出的最大利润
            thirdSell = max(thirdSell, thirdBuy + prices[i]);
        }
 
        return thirdSell;
    }
};

seems to have some idea.

I always think about one thing, if I had a mirror space, I could spare a whole life to learn how to code. After that, I enter another space to learn how to design. And go on studying playing balls and so on. However, I have only one time in this world and what I want to learn is too much with lazy mind. Rue always happen. I do some videos to record my travel and rember peoples whit me. Attracting fans sounds good but self happy means everythin. And guess what, I'll go on. Spare time from tiktok to code or work need some courage, and now I have some. All day's work just prove the plan not work, that's works do.

Chris Gardner, a stock trader, played in stocks. In the persuit of happyness, to be honest, I like this moment. Say yes to himself, in variable lives.

back to the topic, idea is find the fimilar things.

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.empty()) return 0;
 
        int n = prices.size();
        // 初始化状态变量
        int firstBuy = -prices[0];  // 第一次买入的最大利润
        int firstSell = 0;          // 第一次卖出的最大利润
        int secondBuy = -prices[0]; // 第二次买入的最大利润
        int secondSell = 0;         // 第二次卖出的最大利润
        int thirdBuy = -prices[0];  // 第三次买入的最大利润
        int thirdSell = 0;          // 第三次卖出的最大利润

        int No.Buy = - prices[0];
        int No.Sale = 0;



 
        return thirdSell;
    }
};

the loop could do the same:

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.empty()) return 0;
 
        int n = prices.size();
        // 初始化状态变量
        int firstBuy = -prices[0];  // 第一次买入的最大利润
        int firstSell = 0;          // 第一次卖出的最大利润
        int secondBuy = -prices[0]; // 第二次买入的最大利润
        int secondSell = 0;         // 第二次卖出的最大利润
        int thirdBuy = -prices[0];  // 第三次买入的最大利润
        int thirdSell = 0;          // 第三次卖出的最大利润

        int No.Buy = - prices[0];
        int No.Sale = 0;


        for (int i = 1; i < n; ++i) {
            // 更新第一次买入的最大利润
            firstBuy = max(firstBuy, -prices[i]);
            // 更新第一次卖出的最大利润
            firstSell = max(firstSell, firstBuy + prices[i]);
            // 更新第二次买入的最大利润
            secondBuy = max(secondBuy, firstSell - prices[i]);
            // 更新第二次卖出的最大利润
            secondSell = max(secondSell, secondBuy + prices[i]);
            // 更新第三次买入的最大利润
            thirdBuy = max(thirdBuy, secondSell - prices[i]);
            // 更新第三次卖出的最大利润
            thirdSell = max(thirdSell, thirdBuy + prices[i]);

No.Buy = max(No.Buy, No.-1Buy - prices[I]);
No.Sale = max(No.Sale, No.Sale + prices[I]);
        }
 
        return No.Sell;


    }
};

Even people who doesnot know the code knows that the code doesnot runs, need some magic.

Now have two variables, i day and k times.

Define dp[i][j], the maximum profit in i days and trade j times. Then the most signifiicant eauation can be writed as 

dp[i][j][sale] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i])

dp[i][j][buy] = max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i])

This method can easilly understood while the array comes to three-dimentional which is really hard to caculated. I can solve two-dimentional array problems. However, the three is a little bit hard.

For each day, you have two options, have the stock or donot have the stock.

For have the stock, you may have it yesterday or buy it today. So the maximum profit is

 buy[j] = max(buy[j], sell[j - 1] - prices[i]);

For donot have the stock, you may sold it yesterday or sold it today, so the maximum profit is

sell[j] = max(sell[j], buy[j] + prices[i]);

Maybe it works but I am not sure, take a example:

prices = {3, 2, 6, 5, 0, 3};
k = 2

day 0, price is 3

• j=1:
• buy[1] = max(buy[1], sell[0]-3) = max(INT_MIN, 0-3) = -3
• sell[1] = max(sell[1], buy[1]+3) = max(0, -3+3) = 0
• j=2:
• buy[2] = max(buy[2], sell[1]-3) = max(INT_MIN, 0-3) = -3
• sell[2] = max(sell[2], buy[2]+3) = max(0, -3+3) = 0

day 1，price = 2

• j=1:
• buy[1] = max(-3, sell[0]-2) = max(-3, 0-2) = -2
• sell[1] = max(0, -2+2) = 0
• j=2:
• buy[2] = max(-3, sell[1]-2) = max(-3, 0-2) = -2
• sell[2] = max(0, -2+2) = 0

day 2，price = 6:

• j=1:
• buy[1] = max(-2, 0-6) = -2
• sell[1] = max(0, -2+6) = 4
• j=2:
• buy[2] = max(-2, 4-6) = -2
• sell[2] = max(0, -2+6) = 4

day 3，price = 5:

• j=1:
• buy[1] = max(-2, 0-5) = -2
• sell[1] = max(4, -2+5) = 4
• j=2:
• buy[2] = max(-2, 4-5) = -2
• sell[2] = max(4, -2+5) = 4

day 4，price = 0:

• j=1:
• buy[1] = max(-2, 0-0) = 0
• sell[1] = max(4, 0+0) = 4
• j=2:
• buy[2] = max(-2, 4-0) = 4
• sell[2] = max(4, 4+0) = 4

day 5，price = 3:

• j=1:
• buy[1] = max(0, 0-3) = 0
• sell[1] = max(4, 0+3) = 4
• j=2:
• buy[2] = max(4, 4-3) = 4
• sell[2] = max(4, 4+3) = 7

OK, it works.

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
  
        int n = prices.size();

        vector<int> buy(k + 1, INT_MIN), sell(k + 1, 0);
        for (int i = 0; i < n; i++) {
            for (int j = 1; j <= k; j++) {
                // 更新买入状态，即在第i天买入第j次的最大利润
                buy[j] = max(buy[j], sell[j - 1] - prices[i]);
                // 更新卖出状态，即在第i天卖出第j次的最大利润
                sell[j] = max(sell[j], buy[j] + prices[i]);
            }
        }
        // 最后返回卖出状态的最大值，即进行k次交易的最大利润
        return sell[k];
    }
};

This week having some works to do. To be honest, this tipic is a little bit hard which takes me few days to work it. 
 

Anyway, happy weekend.