Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

# preface

The best time to buy and sell stocks III is as follows:

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 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).

# A, thinking

The best time to buy and sell a stock is the same as the best time to buy and sell a stock on the same day.

If we split the stock into each day, we would have the following five states for each day:

1. Do nothing, the profits will always be, right`0`
2. First purchase
3. First sale
4. Second purchase
5. Second sale

The first state we can ignore for the moment and focus on the following four states.

If we can determine the status of the previous day, we can easily extrapolate today’s profits. The state transition is as follows:

• `First buy today``Stay put or buy today's stock`(Today’s stock may be cheaper, buy cheaper to maximize profits)
• `First sale today``Sold once before or bought once before and sold today`
• `Second buy of the day``Stay put or buy today's stock`
• `Second sale today``Sold twice before or bought twice before and sold today`

## Dynamic programming

We can easily solve this problem using dynamic programming based on the above reasoning. Let the four lines in DP [][4] correspond to the first buy, the first sell, the second buy and the second sell respectively

### Dealing with boundary cases

Dp [0][0] = -prices[0]

### State transition equation

``````dp[i][0] = Math.max(dp[i-1][0], -prices[i])
dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i])
dp[i][2] = Math.max(dp[i-1][2], dp[i-1][1] - prices[i])
dp[i][3] = Math.max(dp[i-1][3], dp[i-1][2] + prices[i])
Copy the code``````

In order to show that the operation did not occur, we set the default value of the array to null. Therefore, when dealing with the second buy and second sell, the need for the previous day’s first sell and second buy non-empty judgment!

# Second, the implementation

### The implementation code

The code is completely consistent with the idea, although the efficiency is a little lower, but can better understand the process of dynamic planning.

``````    public int maxProfit(int[] prices) {
int len = prices.length;
Integer[][] dp = new Integer[len][4];
dp[0] [0] = -prices[0];  // First day only
// Handle return values to prevent null Pointers
dp[len-1] [1] = -1;
dp[len-1] [3] = -1;
for (int i = 1; i < len; ++i) {
// Stay put or buy today's stocks
dp[i][0] = Math.max(dp[i-1] [0], -prices[i]);
// Sold once before or bought once before sell today
if (dp[i-1] [1] = =null){
dp[i][1] = dp[i-1] [0] + prices[i];
}else {
dp[i][1] = Math.max(dp[i-1] [1], dp[i-1] [0] + prices[i]);
}
if (dp[i-1] [1] != null) {if (dp[i-1] [2] != null){
dp[i][2] = Math.max(dp[i-1] [2], dp[i-1] [1] - prices[i]);
}else {
dp[i][2] = dp[i-1] [1] - prices[i]; }}// Sold twice before or sold again today
if (dp[i-1] [2] != null) {if (dp[i-1] [3] != null){
dp[i][3] = Math.max(dp[i-1] [3], dp[i-1] [2] + prices[i]);
}else {
dp[i][3] = dp[i-1] [2] + prices[i]; }}}return Math.max(Math.max(dp[len-1] [1], dp[len-1] [3]),0);
}
Copy the code``````

### The test code

``````    public static void main(String[] args) {
int[] nums = {3.3.5.0.0.3.1.4};
int[] nums1 = {1.2.3.4.5};
int[] nums2 = {1};
new Number123().maxProfit(nums2);
}
Copy the code``````

# Third, summary

Thank you to see the end, very honored to help you ~♥

If you think my writing is good, you might as well give me a thumbs-up! If you have any questions, please see the comments section