Leetcode（122）—— The best time to buy and sell stocks II

subject

Give you an array of integers prices , among prices[i] Represents a stock i Sky price .

Every day , You can decide whether to buy and / Or sell shares . You at any time most Can only hold A wave of Stocks . You can also buy... First , And then in On the same day sell .

return What you can get Maximum profits .

Example 1：

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

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 .
The total profit is 4 .

Example 3：

Input ：prices = [7,6,4,3,1]
Output ：0
explain ： under these circumstances , There is no positive profit from trading , So you can get the maximum profit by not participating in the transaction , The biggest profit is 0 .

Tips ：

• $1$ <= prices.length <= $3\ast 10^4$
• $0$ <= prices[i] <= $10^4$

Answer key

Method 1 ： greedy

Ideas

​​   Because there are no restrictions on the purchase of shares , So the whole problem is equivalent to finding $x$ Two disjoint intervals $(l_i,r_i]$ Maximize the following equation
$$\sum _{i=1}^{x}a[r_i]-a[l_i]$$

​​   among $l_i$ Said in the first $l_i$ Sky buying ,$r_i$ Said in the first $r_i$ Day sell .

​​   At the same time, we note that for $(l_i,r_i]$ The value contributed by this interval $a[r_i]-a[l_i]$, In fact, it's equivalent to $(l_i,l_i+1],(l_i+1,l_i+2],\dots ,(r_i-1,r_i]$ The length of these intervals is 11 The value of the interval and , namely
$$a[r_i]-a[l_i]=(a[r_i]-a[r_i-1])+(a[r_i-1]-a[r_i-2])+\dots +(a[l_i+1]-a[l_i])$$

​​   therefore The problem can be simplified by look for $x$ A length of $1$ The range of $(l_i,l_i+1]$ bring ${\sum }_{i=1}^{x}a[l_i+1]-a[l_i]$ Maximize value .

​​   From the perspective of greed, each time we choose to contribute more than $0$ The interval of can maximize the answer , So the final answer is
$$\text{ans}=\sum _{i=1}^{n-1}\max \{0,a[i]-a[i-1]\}$$

​​   among $n$ Is the length of the array .

​​   It should be noted that , The greedy algorithm can only be used to calculate the maximum profit , The calculation process is not the actual transaction process .

​​   Consider the examples in the topic $[1,2,3,4,5]$, Length of array $n=5$, Because of all the $1\le i<n$ There are $a[i]>a[i-1]$, So the answer is
$$\text{ans}=\sum _{i=1}^{n-1}a[i]-a[i-1]=4$$

​​   however The actual transaction process is not $4$ Second purchase and $4$ Time to sell , But in the $1$ Sky buying , The first $5$ Day sell .

Code implementation

class Solution {
    
public:
    int maxProfit(vector<int>& prices) {
    
        int ans = 0, size = prices.size();
        if(size <= 1) return 0;
        for (int i = 1; i < size; i++) {
    
            if (prices[i] > prices[i-1]) {
      //  It is profitable to sell 
                ans += (prices[i] - prices[i-1]);
            }
        }
        return ans;
    }
};

Leetcode Official explanation ：

class Solution {
    
public:
    int maxProfit(vector<int>& prices) {
       
        int ans = 0;
        int n = prices.size();
        for (int i = 1; i < n; ++i) {
    
            ans += max(0, prices[i] - prices[i - 1]);	//  The difference between adjacent two is in descending order +0
        }
        return ans;
    }
};

Complexity analysis

Time complexity ：$O(n)$, among $n$ Is the length of the array . We just need to traverse the array once .
Spatial complexity ：$O(1)$. You just need constant space to hold a few variables .

Method 2 ： Dynamic programming

Ideas

​​   in consideration of 「 You can't participate in multiple transactions at the same time 」, Therefore, after the end of trading every day, there may only be a stock or no stock in hand .

​​   Define the State $\text{dp}[i][0]$ It means the first one $i$ I don't have the maximum profit of the stock in my hand after trading ,$\text{dp}[i][1]$ It means the first one $i$ The biggest profit of holding a stock after a day's trading （$i$ from $0$ Start ）.

​​   consider $\text{dp}[i][0]$ Transfer equation of , If there is no stock in hand after trading on this day , Then the possible transition state is that there are no stocks the day before , namely $\text{dp}[i-1][0]$, Or hold a stock at the end of the previous day , namely $\text{dp}[i-1][1]$, At this time we have to sell it , And get $\text{prices}[i]$ Revenue . So in order to maximize revenue , We list the following State transition equation ：
$$\text{dp}[i][0]=\max \{\text{dp}[i-1][0],\text{dp}[i-1][1]+\text{prices}[i]\}$$

​​   Consider again $\text{dp}[i][1]$, Consider the transition state in the same way , Then the possible transfer status is that you have held a stock the previous day , namely $\text{dp}[i-1][1]$, Or there were no stocks at the end of the previous day , namely $\text{dp}[i-1][0]$, At this time, we want to buy it , And reduce $\text{prices}[i]$ Revenue . You can list the following State transition equation ：
$$\text{dp}[i][1]=\max \{\text{dp}[i-1][1],\text{dp}[i-1][0]-\text{prices}[i]\}$$

​​   about The initial state , According to the definition of state, we can know that $0$ At the end of the day $\text{dp}[0][0]=0$,$\text{dp}[0][1]=-\text{prices}[0]$.

​​   therefore , We just need to calculate the state from front to back . Because after the end of all transactions , The income from holding shares must be lower than that from not holding shares （ Buy stocks and spend money , crap ）, So this time $\text{dp}[n-1][0]$ The benefits must be greater than $\text{dp}[n-1][1]$ Of , The final answer is $\text{dp}[n-1][0]$.

​​   Notice that in the state transfer equation above , The state of each day is only related to the state of the previous day , It has nothing to do with earlier states , So we don't have to store these irrelevant States , Only need to $\text{dp}[i-1][0]$ and $\text{dp}[i-1][1]$ Stored in two variables , They calculate $\text{dp}[i][0]$ and $\text{dp}[i][1]$ Coexist back to the corresponding variable , So that the second $i+1$ The state of days can be transferred .

Code implementation

Leetcode Official explanation ：

class Solution {
    
public:
    int maxProfit(vector<int>& prices) {
    
        int n = prices.size();
        int dp0 = 0, dp1 = -prices[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 dp0;
    }
};

Complexity analysis

Time complexity ：$O(n)$, among $n$ Is the length of the array . Altogether $2n$ Status , The time complexity of each state transition is $O(1)$, So the time complexity is zero $O(2n)=O(n)$.
Spatial complexity ：$O(n)$. We need to open up $O(n)$ All States in spatial storage dynamic planning . If space optimization is used , The space complexity can be optimized to $O(1)$.