Cartoon: looking for the best time to buy and sell stocks

————— the second day —————

What does that mean ？ Let's take an example , Given the following array ：

The corresponding stock up and down curve of this array is as follows ：

obviously , From 2 The price is 1 Buy when , From 5 The price is 8 Sell when , You can get the most out of it ：

The biggest payoff at this point is 8-1=7.

In the example above , Maximum 9 At the minimum 1 In front of , How can we trade ？ We can't turn back time ？

————————————

The following is an example , If we have set the price 4 It's time to sell , So which is the best time to buy ？

We have to choose the price 4 The previous interval , And must be the minimum value in the interval , obviously , The best choice is price 2 The timing of the .

The first 1 Step , Initialization operation , Put the first 1 Elements as temporary minimum price ; The initial value of maximum return is 0：

The first 2 Step , Traverse to the 2 Elements , because 2<9, So the current minimum price becomes 2; There is no need to calculate the difference （ Because the front element is bigger than it ）, The biggest benefit is still 0：

The first 3 Step , Traverse to the 3 Elements , because 7>2, So the current minimum price is still 2; As we said just now , Suppose the price 7 For selling point , The best buy point for that is the price 2, The difference between the two 7-2=5,5>0, So the biggest payoff right now is 5：

The first 4 Step , Traverse to the 4 Elements , because 4>2, So the current minimum price is still 2;4-2=2,2<5, So the biggest payoff is still 5：

The first 5 Step , Traverse to the 5 Elements , because 3>2, So the current minimum price is still 2;3-2=1,1<5, So the biggest payoff is still 5：

And so on , We walk through the end of the array , The minimum price at this time is 1; The biggest benefit is 8-1=7：

public class StockProfit {

    public static int maxProfitFor1Time(int prices[]) {
        if(prices==null || prices.length==0) {
            return 0;
        }
        int minPrice = prices[0];
        int maxProfit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] < minPrice) {
                minPrice = prices[i];
            } else if(prices[i] - minPrice > maxProfit){
                maxProfit = prices[i] - minPrice;
            }
        }
        return maxProfit;
    }

    public static void main(String[] args) {
        int[] prices = {9,2,7,4,3,1,8,4};
        System.out.println(maxProfitFor1Time(prices));
    }

}

Copy

Before each purchase , You have to sell your shares . Let's take the array in the following figure for example , Take a visual look at the timing of buying and selling ：

In the picture , The green line represents the stage of price rise . Since there is no limit to the number of transactions , So we can buy at every low point , Sell at every high .

thus , All the green parts are our gains , The maximum total return is the sum of these local returns ：

（6-1）+（8-3）+（4-2）+（7-4） = 15

As for how to judge these green rising stages ？ It's simple , We traverse the entire array , But where the latter is greater than the former , It means that the stock price is in the rising stage .

    public int maxProfitForAnyTime(int[] prices) {
        int maxProfit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i-1])
                maxProfit += prices[i] - prices[i-1];
        }
        return maxProfit;
    }

Copy

—————END—————