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 or sell stocks is as follows:

Given an array prices, its ith element prices[I] represents the price of a given stock on day I.

You can only buy the stock on one day and sell it on a different day in the future. Design an algorithm to calculate the maximum profit you can make.

Return the maximum profit you can make from the transaction. If you can’t make any profit, return 0.

Example 1:

Input: [7,1,5,3,6,4] output: 5 explanation: buy on day 2 (stock price = 1) and sell on day 5 (stock price = 6), maximum profit = 6-1 = 5. Note that the profit cannot be 7-1 = 6, because the selling price needs to be higher than the buying price; Also, you can't sell stocks before you buy them.Copy the code

Example 2:

Input: prices = [7,6,4,3,1] output: 0 explanation: in this case, no transaction is completed, so the maximum profit is 0.Copy the code

A, thinking

The purpose of this question is to calculate the maximum profit from buying and selling stocks, but we need to pay attention to the following rules:

  • The date of purchase must precede the date of sale
  • If there is no suitable buying and selling date, the profit is0. (For example, in the examplePrices =,6,4,3,1 [7], how to buy and sell are losses, so can not move)
  • You can only buy a stock once on a given day, and you can only sell it once on a later day

The most notable aspect of the above rule is that the whole process from buy to sell can only happen once. We can think of the daily stock prices as a line chart (date on the X-axis), using example 1 [7,1,5,3,6,4] as an example.

For the maximum profit that can be made on a given day, subtract the minimum from the previous price from the current value. Assuming that the selling date is the fourth day, the maximum profit of selling on the fourth day is 3-1 = 2.

To sum up: The maximum profit sold on day I is the current price minus the historical low price (before the current date)

After the above analysis, the realization steps can be roughly divided into the following two steps:

  1. Initialize a one-dimensional arrayminArrUsed to store historically low prices
  2. So let’s iterate to figure out from1 ~ iTake the maximum profit of the day

Second, the implementation

The implementation code

The implementation code is consistent with the idea

    public int maxProfit(int[] prices) {
        int len = prices.length;
        int[] minArr = new int[len];
        minArr[0] = prices[0];  // There is no element before the first element
        for (int i=1; i<len; i++){
            minArr[i] = Math.min(minArr[i-1], prices[i]);
        }
        int ret = 0;    / / returns
        for (int i=0; i<prices.length; i++){
            ret = Math.max(ret, prices[i] - minArr[i]);
        }
        return ret;
    }
Copy the code

The test code

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