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 II is as follows:

You are given an array prices, where prices[I] represents the price of the stock on day I.

On each day, you may decide to buy and/or sell shares. You can’t hold more than one share at any time. You can also buy it and sell it on the same day. Return the maximum profit you can make.

Example 1:

Input: prices = [7,1,5,3,6,4] Output: 7 Then, by buying on day 4 (stock price = 3) and selling on day 5 (stock price = 6), the exchange makes a profit = 6-3 = 3.Copy the code

A, thinking

The best time to buy and sell stocks is to maximize profits. But in this case you can buy and sell multiple times.

There are several important points to note in the title:

  • You can buy and sell multiple times over a period of time
  • You can hold no more than one stock in a day

Note that for each day, there can only be two states: either you own a stock or you don’t own a stock, so let’s just store the returns from owning and not owning a stock in the array.

Dynamic programming

We use two one-dimensional arrays to store the corresponding benefits of the two states:

  • dpNot[]: Does not currently own shares
  • dpHas[]: Hold the stock of the day

Boundary case:

DpNot [0] = 0 dpHas[0] = -prices[0]

The state transition equation is as follows:

On day I, if no stock is held, it is the maximum value of no stock held on the previous day or the maximum value of stock held on the previous day but sold today. On day I, if you own stocks, you also owned stocks on the previous day or you didn’t own stocks on the previous day but bought stocks today.

dpNot[i] = Math.max(dpNot[i - 1], dpHas[i - 1] + prices[i])
dpHas[i] = Math.max(dpHas[i - 1], dpNot[i - 1] - prices[i])
Copy the code

We iterate over all days, initialize all returns for holding or not holding stocks, and then return the returns dpNot[len] that we did not hold on the last day (we must not hold stocks on the last day because of profit maximization).

Second, the implementation

The implementation code

The implementation code is consistent with the idea

    public int maxProfit(int[] prices) {
        int len = prices.length;
        int[] dpNot = new int[len];   / / do not hold
        int[] dpHas = new int[len];   / / hold
        dpNot[0] = 0;   // The first day selling gain is 0
        dpHas[0] = -prices[0];  // Hold returns are negative on the first day
        for (int i = 1; i < len; ++i) { // From the next day
            // Compare current holding and selling profits
            dpNot[i] = Math.max(dpNot[i - 1], dpHas[i - 1] + prices[i]);
            dpHas[i] = Math.max(dpHas[i - 1], dpNot[i - 1] - prices[i]);
        }
        return dpNot[len - 1];
    }
Copy the code

The test code

public static void main(String[] args) {
    int[] nums = {7.1.5.3.6.4};
    new Number122().maxProfit(nums);
}
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