Greed 122. The best time to buy and sell stocks II

1 Title Description

122. The best time to buy and sell stocks II
     Give you an array of integers prices , among prices[i] Represents a stock i Sky price .

Every day , You can decide whether to buy and / Or sell shares . You at any time most Can only hold A wave of Stocks . You can also buy... First , And then in On the same day sell .

return What you can get Maximum profits .

2 Title Example

Example 1：
Input ：prices = [7,1,5,3,6,4]
Output ：7
explain ： In the 2 God （ Stock price = 1） Buy when , In the 3 God （ Stock price = 5） Sell when , The exchange will make a profit = 5 - 1 = 4 .
And then , In the 4 God （ Stock price = 3） Buy when , In the 5 God （ Stock price = 6） Sell when , The exchange will make a profit = 6 - 3 = 3 .
The total profit is 4 + 3 = 7 .

Example 2：
Input ：prices = [1,2,3,4,5]
Output ：4
explain ： In the 1 God （ Stock price = 1） Buy when , In the 5 God （ Stock price = 5） Sell when , The exchange will make a profit = 5 - 1 = 4 .
The total profit is 4 .

Example 3：
Input ：prices = [7,6,4,3,1]
Output ：0
explain ： under these circumstances , There is no positive profit from trading , So you can get the maximum profit by not participating in the transaction , The biggest profit is 0 .

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii

3 Topic tips

1 <= prices.length <= 3 * 10⁴
0 <= prices[i] <= 10⁴

4 Ideas

First of all, this topic should be clear about two points :

• Only one stock !
• At present, only the operation of buying or selling stocks

It takes at least two days for a trading unit to make a profit .

Maybe we just want to , Choose a low buy , Choose a high one to sell , Choose a low buy … Cyclic repetition .
If we think that the final profit can be decomposed , So the problem is very easy !
How to decompose ?
If No 0 Sky buying , The first 3 Day sell , Then the profit is : prices[3] - prices[0].
amount to (prices[3] - prices[2])+ (prices[2] - prices[1])+(prices[1] - prices[o]). At this time, the profit is decomposed into the dimension of daily unit , Not from o To the first day 3 Think about it as a whole !
So according to prices You can get the daily profit sequence :(prices[i] - prices[i - 1……(prices[1] - prices[0]).

— Some students fall into : Why is there no profit on the first day , In the confusion of whether the first day was counted or not .
Of course there was no profit on the first day , It won't be profitable until at least the next day , So the sequence of profits is less than that of stocks — God !
As you can see from the diagram , In fact, we need to collect positive profits every day , Collect positive profit intervals , Is the range of stock trading , And we just need to focus on the final profit , There is no need to record the interval .
Then only collecting positive profits is what greed is greedy for !
Local optimum : Collect daily positive profits , The best in the world : To maximize profits .
Local optimum can deduce global optimum , No counterexample , try — Try greed !

5 My answer

//  Greedy thought 
class Solution {
    
    public int maxProfit(int[] prices) {
    
        int result = 0;
        for (int i = 1; i < prices.length; i++) {
    
            result += Math.max(prices[i] - prices[i - 1], 0);
        }
        return result;
    }
}