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

The title

Given an array of integers prices, prices[I] represents the stock price on day I; The round fee represents the processing fee for trading stocks.

You can complete transactions as many times as you want, but you have to pay a fee for each transaction. If you have already bought a stock, you cannot continue to buy it until you have sold it.

Returns the maximum profit earned.

Note: a transaction refers to the entire process of buying, holding and selling a stock, and you only have to pay a fee for each transaction.

Example 1:

Input: prices = [1, 3, 2, 8, 4, 9], fee = 2 Output: 8 Explanation: Maximum profit that can be achieved: Prices [0] = 1 Prices [3] = 8 Prices [4] = 4 Prices [5] = 9 Total profit: (), (8-1-2) + (a) (9-4-2) = 8 example 2: input: prices =,3,7,5,10,3 [1], fee = 3 output: 6Copy the code

Tip:

1 <= prices.length <= 5 * 104
1 <= prices[i] < 5 * 104
0 <= fee < 5 * 104
Copy the code

Answer key

Analysis of the problem solving

Description: Given an array of daily stock prices, you can choose whether to buy/sell every day, and cannot buy again when holding. Each transaction has a fixed handling fee, so as to obtain the maximum profit.

Answer:

  1. As we can see from the title, this is a typical dynamic programming problem.
  2. For dynamic programming, we can summarize the following ideas:
    • Define the state transition equation
    • Given the initial value of the transfer equation
    • The equations are first transferred by code recursion
  3. We first define the transfer equation

Define a two-dimensional array dp[n][2]:

  • Dp [I][1] represents the maximum profit that can be obtained on day I without holding;
  • Dp [I][2] represents the maximum profit gained by holding on day I (note: hold on day I, not buy on day I).

Define the transfer equation:

  • Don’t hold: dp [I] [0] = Max (dp [0], [I – 1] dp [1] [I – 1] + price [I] – fee)

For today do not hold, can be transferred from two states, 1. Yesterday did not hold; 2. Hold yesterday, sell today. Get maximum value

  • Hold: dp [I] [1] = Max (dp [1], [I – 1] dp [0] – [I – 1] price [I])

For today, can be transferred from two states, 1. Yesterday also held; Don’t hold yesterday, buy today, get maximum

  1. Initialize the transfer equation

For day 0: – do not hold: dp[0][0] = 0; – Hold (ie buy) : dp[0][1] = -prices[0];

  1. Code to implement the transfer equation
class Solution {
    public int maxProfit(int[] prices, int fee) {
        int n = prices.length;
        int[][] dp = new int[n][2];
        dp[0] [0] = 0;
        dp[0] [1] = -prices[0];
        for (int i=0; i< n; i++) {
           dp[i][0] = Math.max(dp[i-1] [0], dp[i -1] [1] + prices[i] - fee);
           dp[i][1] = Math.max(dp[i-1] [1], dp[i-1] [0] - prices[i]);
        }
        return dp[n-1] [0]; }}Copy the code

Since we only need the data of the previous time, we can carry out spatial optimization. During the transfer, DP [I] is transferred from DP [i-1], so we can remove the one-dimensional array. The final solution code is shown.

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, int fee) {
        int n = prices.length;
        // Sell indicates the maximum profit from a sale
        int sell = 0, buy = -prices[0];
        for (int i = 1; i < n; i++) {
            sell = Math.max(sell, buy + prices[i] - fee);
            buy = Math.max(buy, sell - prices[i]);
        }
        returnsell; }}Copy the code

Feedback results after submission:

The reference information

  • Best time to buy or sell stocks includes the freeze period
  • LeetCode dynamic programming of the best time to buy or sell stocks includes the freeze period