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, right0
  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]);
            }
            // Hold or buy once before and buy today
            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

The results of

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