This is the 13th day of my participation in the First Challenge 2022, for more details: First Challenge 2022 “.

123. The best time to Buy and sell stocks III

Topic describes

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

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 1:

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

parsing

/** * @brief dynamic programming * 1, determine the dp array and the meaning of the subscript * * (0) No operation * (1) First buy stock * (2) First sell stock * (3) second buy stock * (4) second sell stock * * 2, determine the recursive formula * dp[I][1]: * Buy stock: Dp [I] [1] = dp [0] - [I - 1] prices without operation: [I] * dp [I] [1] = dp [I - 1] [1] * dp [I] [1] = Max (buying stocks, no operation) * dp [I] [2] : * to sell: dp [I] [2] = dp [1] + [I - 1] prices [I] * no operation: dp [I] [2] = dp [1] [I - 1] * dp [I] [2] = Max (sell shares, no operation) * * dp [I] [3] : * to buy stocks: dp [I] [3] = dp [I - 1] [2] - prices without operation: [I] * dp [I] [3] = dp [I - 1] [3] * dp [I] [3] = Max (buying stocks, no operation) * * dp [I] [4] : * to sell: dp [I] [4] = dp [I - 1] [3] + prices [I] * no operation: dp [I] [4] = dp [I - 1] [3] * dp [I] [4] = Max (sell shares, no operation) 3, initialize an array of * * * first day without operation: * dp[0][1] = -prices[0] * dp[0][2] = 0 * dp [0] [3] = - prices [0] * sold on the first day of the second: * dp [0] [4] = 0 * * /
Copy the code

code

class Solution
{
public:
    int maxProfit(vector<int> &prices)
    {
        int len = prices.size(a); vector<vector<int>> dp(len, vector<int> (5.0));
        dp[0] [1] = -prices[0];
        dp[0] [3] = -prices[0];

        for (int i = 1; i < len; i++)
        {
            dp[i][0] = dp[i - 1] [0];
            dp[i][1] = max(dp[i - 1] [0] - prices[i], dp[i - 1] [1]);
            dp[i][2] = max(dp[i - 1] [1] + prices[i], dp[i - 1] [2]);
            dp[i][3] = max(dp[i - 1] [2] - prices[i], dp[i - 1] [3]);
            dp[i][4] = max(dp[i - 1] [3] + prices[i], dp[i - 1] [4]);
        }

        return dp[len - 1] [4]; }};Copy the code