Topic Description (Easy Difficulty)

As in problem 121, given an array representing daily prices. The difference is that problem 121 can only be bought or sold once. But this problem can continue to buy and sell, but only after selling can continue to buy.

Method a

Just using the simplest idea, we go back in time, and we know what the stock price is going to be every day in the future. How do we do that?

Sell the day before the fall, as in the following example

1 2 3 4 天
2 7 8 5

第 4If the day goes down, we can sell the day before, buy again the day after the day goes down, and sell again the day beforeCopy the code

Two special cases need to be considered

All the way up, not down

1 3 5 9Then we can sell it on the last dayCopy the code

Fall the next day

8 7 9 10When it goes down, we should have sold it the day before, but we can only buy it on the first day, not sell it, so it doesn't make any gainsCopy the code

After considering all of the above, you can write code.

public int maxProfit(int[] prices) {
    int profit = 0;
    int buy = 0;
    int sell = 1;

    for (; sell < prices.length; sell++) {
        // There is a drop
        if (prices[sell] < prices[sell - 1]) {
            // Not the second day down, just the day before the sale, cumulative gains
            if(sell ! =1) {
                profit += prices[sell - 1] - prices[buy];
            }
            // Buy again on the day of the drop
            buy = sell;
        
        // If it goes up on the last day, sell on the last day
        } else if (sell == prices.length - 1) { profit += prices[sell] - prices[buy]; }}return profit;
}
Copy the code

There is also the case of a continuous decline

9 8 7 3 2But for our code, if it keeps going down, buy and sell -1It's going to be the same, so it's going to accumulate0, does not affect the resultCopy the code

Method 2

In fact, we don’t have to think about that much, and let’s be direct, as long as the current day is up relative to the previous day, we buy the previous day, sell the current day.

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

The total

The above two solutions are based on the actual situation, to consider the maximum profit. The official way of understanding is also very good, here to share.

Both solutions can be abstracted from the diagram above.

Solution one, in fact, every time you take the difference between the trough and the crest, and then you add up all the differences.

The second solution is to find the rising polyline segment, and the height of all the rising polyline segment is accumulated.

So some of the questions, maybe the code is the same, but the meaning is not the same.

See Leetcode.Wang for more details on popular problems.