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

The title

The timing of buying and selling stocks includes the freeze period

Given an array of integers prices, prices[I] represents the stock price on day I.

Design an algorithm to calculate the maximum profit. You can make as many trades (buying and selling a stock multiple times) as you can with the following constraints:

After selling, you cannot buy the stock the next day (i.e. freeze period is 1 day). Note: You can’t participate in more than one transaction at a time (you must sell your previous shares before buying again).

Example 1:

Input: prices = [1,2,3,0,2] Output: 3 Description: The corresponding trading states are: [Buy, Sell, freeze, Buy, sell] Example 2: Input: prices = [1] Output: 0Copy the code

Tip:

1 <= prices.length <= 5000
0 <= prices[i] <= 1000
Copy the code

Answer key

Analysis of the problem solving

Antithesis thought

  1. We can only buy one stock at a time, and we have three different states on any given day.

    • We currently own a stock whose “cumulative maximum return” is f0;
    • We currently do not own any shares and are in the freeze period, and the corresponding “cumulative maximum return” is denoted as F1
    • We do not currently own any shares and are not in a freeze period, and the corresponding “cumulative maximum return” is denoted as F2

  2. So let’s do the analysis around three states.

    • If you currently own the stock for the maximum returnf0 = max(f1, f2 - price[i])
    • If the day is difficult to freeze the current maximum benefitf1 = f0 + price[i]
    • If the day is not in the freezing period, the maximum yield of Dan lead isf2 = max(f1, f2)

  3. We simply iterate through the three values and return the appropriate result

Complexity analysis

  • Time complexity: O(N)
  • Space complexity: O(1), we did not create additional arrays to store.

The problem solving code

The solution code is as follows (there are detailed notes in the code) :

class Solution {
    public int maxProfit(int[] prices) {
        // Determine valid parameters
        if (prices == null || prices.length == 0) {
            return 0;
        }
        // Get a number of long reads
        int n = prices.length;
        // F0, f1, and f2 default values are -prices[0], 0, 0, respectively
        // Because the first day is negative
        int f0 = -prices[0], f1 = 0, f2 = 0;
        for (int i = 1; i < n; i++) {
            int newf0 = Math.max(f0, f2 - prices[i]);
            int newf1 = f0 + prices[i];
            int newf2 = Math.max(f1, f2);

            f0 = newf0;
            f1 = newf1;
            f2 = newf2;
        }
        returnMath.max(f1, f2); }}Copy the code

Feedback results after submission:

The reference information

  • Best time to buy or sell stocks includes the freeze period