They say you can trade an infinite number of times. And because, for a scheme that buys on day I and sells on day J, the profit is equal to prices[j] – prices[I], that is, it depends only on the prices on the day that the transaction is bought and sold. Therefore, a transaction spanning several consecutive days can be divided into several consecutive transactions spanning one day.

So we only need to choose the “two days” where we can make a profit (buy one day and sell the next), and on each of the two days that we can make a profit, we can capture the difference between the two days as profit.

Just walk through the array: find all the two days you can make a profit, and add up all the differences.

The code is as follows:

class Solution { public: int maxProfit(vector<int>& prices) { int size = prices.size(); int res = 0; for(int i = 0; i < size - 1; ++i) { if(prices[i] < prices[i + 1]) { res += prices[i + 1] - prices[i]; } } return res; }};Copy the code

There is also a more general state machine DP solution to the stock series problem, which can be referred to the best time to buy and sell stocks IV.

Dp [I][k][0 or 1] can be used to indicate that the current number of days is I, the maximum number of transactions allowed at present is K, and the maximum profit that can be obtained by holding the stock at the current time (0 means no holding, 1 means holding). Since the number of transactions k in this problem is infinite, that is, there is no limit on the number of transactions K, we only need the two-dimensional array DP [I][0 or 1] to represent the maximum profit of holding or not holding the stock on day I.

Dp [I][0] = dp[i-1][0]; dp[I] = dp[i-1][0]; Dp [I][0] = dp[i-1][1] + prices[I]; Dp [I][0] = Max (dp[i-1][0], dp[i-1][1] + prices[I]); dp[I] = Max (dp[i-1][0]);

For dp[I][1], which is a holding state, it also has two transitions, that is, the previous holding of the stock: dp[I][1] = dp[i-1][1]; Dp [I][1] = dp[i-1][1] -prices [I]; (minus prices[I] means prices[I] cost of buying a stock.) Since the dp array represents the maximum return for the current state, we also need a Max for both states: dp[i][1] = max(dp[i – 1][1], dp[i – 1][0] – prices[i]);

Since the state transition equation needs the value of DP [i-1][0 or 1] for DP [I][0 or 1], we need to deal with the boundary dp[0][0 or 1].

Obviously dp[0][0] is 0, because on day 0, if I didn’t buy the stock, I didn’t have any money. Dp [0][1] is -prices[0], which means that on day 0, prices[0] buy a stock.

The final result returned is dp[n-1][0](where n is the size of the prices array), which represents the maximum return on the last day without holding the stock. Why not dp[n-1][1]? Since stocks have to be sold to make money, and they cost money to buy, it is clear that DP [n-1][0] is greater than DP [n-1][1].

With the recursive boundary and state transition equation, the code looks like this:

class Solution { public: int maxProfit(vector<int>& prices) { int n = prices.size(); vector<vector<int>> dp(n, vector<int>(2)); for(int i = 0; i < n; ++ I) {if(I == 0) {dp[I][0] = 0; dp[i][1] = -prices[i]; continue; } dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]); dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]); } return dp[n - 1][0]; }};Copy the code