LeetCode best time to buy and sell stocks series summary

This kind of dynamic programming is optimized from two-dimensional dynamic gauge to one-dimensional dynamic gauge. Greed can also be used in some problems.

catalog:

121 the best time to buy and sell stocks 1
122 the best time to buy and sell stocks 2
123the best time to buy and sell stocks 3
188 the best time to buy and sell stocks 4
309 the best time to buy and sell stocks + freezing period
714 best time to buy and sell stocks + handling fee (selling time handling fee based on 2)

121 the best time to buy and sell stocks (once)

Given an array of prices, its ith element prices[i] represents the price of a given stock on day I.
You can only choose to buy this stock one day and sell it on a different day in the future. Design a
Algorithm to calculate the maximum profit you can make.
Return the maximum profit you can make from this transaction. If you can't make any profit, return 0.

Input: [7,1,5,3,6,4]
Output: 5 explanation: buy on day 2 (stock price = 1) and on day 5 (stock price=
6) When selling, the maximum profit = 6-1 = 5.
Note that the profit cannot be 7-1 = 6, because the selling price needs to be greater than the buying price; At the same time, you can't sell stocks before buying.

Two dimensional dynamic gauge
int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if(n == 1)return 0;
        vector<vector<int>>dp(n, vector<int>(2));
        dp[0][0] = 0;                 // Not held = sold + not bought
        dp[0][1] = -prices[0];        // Have bought but not sold
        for(int i = 1; i < n; ++i)
        {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            //Not held on day i = max (not held on day i - 1, held on day i - 1 + sold today)
            dp[i][1] = max(dp[i - 1][1],  -prices[i]);
            //Holding on day i = max (holding on day i - 1, buying today, only once)
        }
        return dp[n - 1][0];
    }

One dimensional kinematic gauge O(N)/O(1)
The status of each day is only related to the status of the previous day dp[i - 1][1],dp[i - 1][0]There are two variables,
Calculated dp[i][1],dp[i][0]Save back the corresponding variable
int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if(n == 1)return 0;
        int sell = 0;                // Not held = sold + not bought
        int buy = -prices[0];        // Have bought but not sold
        for(int i = 0; i < n; ++i)
        {
            int newbuy = max(buy, -prices[i]);
            int newsell = max(sell, buy + prices[i]);
            sell = newsell;
            buy = newbuy;
        }
        return sell;
    }

Greed:
int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if(n == 1)return 0;
        int maxn = 0;
        int start = prices[0];
        for(int i = 1; i < n; ++i)
        {
            if(prices[i] < start) start = prices[i];
            //If the next price is less than the assumed purchase price, update start
            else maxn = max(maxn, prices[i] - start);
            //Update maximum profit
        }
        return maxn;
    }

122 the best time to buy and sell stocks 2 (buy and sell many times)

Give an array prices, where prices[i] is the price of a given stock on day I.
Design an algorithm to calculate the maximum profit you can make. You can complete as many transactions as possible (buying and selling a stock multiple times).
Note: you cannot participate in multiple transactions at the same time (you must sell the previous shares before buying again).

Two dimensional dynamic gauge
 Define status dp[i][1] Represents the second i There is no maximum profit of stocks after trading for days,
dp[i][0] Represents the second i The maximum profit of holding a stock after trading for days( i From 0).
 int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>>dp(n, vector<int>(2));
        dp[0][0] = - prices[0];  //hold
        dp[0][1] = 0;            //Not held
        for(int i = 1; i < n; ++i)
        {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
             //Holding on day i = max (holding on day i - 1, not holding on day i - 1, buying today) and 1 are different
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
        }
        return dp[n - 1][1];
    }
};

One dimensional kinematic gauge
int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int dp0 = -prices[0];
        int dp1 = 0;
        for(int i = 1; i < n; ++i)
        {
            int newdp0 = max(dp0, dp1 - prices[i]);
            int newdp1 = max(dp1, dp0 + prices[i]);
            dp0 = newdp0;
            dp1 = newdp1;
        }
        return dp1;
    }

Greedy, collect all uphill, and is the biggest
 int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int maxn = 0;
        for(int i = 1; i < n; ++i)
        {
            maxn += max(0, prices[i] - prices[i - 1]);
        }
        return maxn;
    }

123 best time to buy and sell stocks (2 times)

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 complete up to two transactions.
Note: you cannot participate in multiple transactions at the same time (you must sell the previous shares before buying again).
Idea: the status of buying twice: no operation, first buying, first selling, second buying, second selling.

Two dimensional dynamic gauge
 int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if(n <= 1)return 0;
        vector<vector<int>>dp(n, vector<int>(5));
        dp[0][0] = 0;                  //No operation
        dp[0][1] = -prices[0];         //First purchase
        dp[0][2] = 0;                  //First sale
        dp[0][3] = -prices[0];         //Second purchase
        dp[0][4] = 0;                  //Second sale
        for(int i = 1; i < n; ++i)
        {
            dp[i][0] = dp[i - 1][0];
            dp[i][1] = max(dp[i - 1][0] - prices[i], dp[i - 1][1]);
            //First buy = max (no operation the day before, buy today, buy the day before)
            dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
            //First sale = max (sold the day before, bought the day before, sold today)
            dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
            //Second buying = max (second buying the day before, first selling the day before + buying today)
            dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
            //Second sale = max (second purchase the day before. Second purchase the day before + sell today)
        }
        return dp[n - 1][4];
    }

 One dimensional dynamic gauge; The status of each day is only related to the status of the previous day
 int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if(n <= 1)return 0;
        int buy1 = -prices[0];
        int sell1 = 0;
        int buy2 = -prices[0];
        int sell2 = 0;
        for(int i = 1; i < n; ++i)
        {
            buy1 = max(buy1, -prices[i]);
            sell1 = max(sell1, buy1 + prices[i]);
            buy2 = max(buy2, sell1 - prices[i]);
            sell2 = max(sell2, buy2 + prices[i]);
        }
        return sell2;
    }

188 best time to buy and sell stocks (k times)

Given an integer array prices, its ith element prices[i] is the price of a given stock on day I.
Design an algorithm to calculate the maximum profit you can make. You can complete up to k transactions.
Note: you cannot participate in multiple transactions at the same time (you must sell the previous shares before buying again).

Two dimensional dynamic gauge
 int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        if(k == 0 || n == 0)return 0;
        vector<vector<int>>dp(n, vector<int>(2*k + 1, 0));
        for(int i = 1; i < 2*k; i += 2) dp[0][i] = -prices[0]; //Odd buy
        for(int i = 1; i < n; i++)
        {
            for(int j = 0; j < 2*k - 1; j += 2)
            {
                dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] -prices[i]);
                dp[i][j + 2] = max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);
            }
        }
        return dp[n - 1][2*k];
    }

309 the best time to buy and sell stocks + freezing period

Given an array of integers, the ith element represents the stock price on day i.
Design an algorithm to calculate the maximum profit. You can complete as many transactions as possible (buying and selling a stock multiple times) under the following constraints:
You cannot participate in multiple transactions at the same time (you must sell the previous shares before buying again).
After selling stocks, you can't buy stocks the next day (i.e. the freezing period is 1 day).

Two dimensional dynamic gauge
 int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>>dp(n, vector<int>(3));
        dp[0][0] = -prices[0];   //hold
        dp[0][1] = 0;            //Not held, frozen
        dp[0][2] = 0;            //Not held, not frozen
        for(int i = 1; i < n; ++i)
        {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][2] - prices[i]);
            //Holding on day i = max (i - holding on day 1, i - not holding on day 1, not buying today)
            dp[i][1] = dp[i - 1][0] + prices[i];
            //Day i not held in frozen = i - 1 just sold
            dp[i][2] = max(dp[i - 1][2],dp[i - 1][1]);
            //Day i not held not frozen = max (i - day 1 not held not frozen, i - day 1 frozen)
        }
        return max(dp[n - 1][1], dp[n - 1][2]);
    }