Given an array, its ith element is the price of a given stock on the ith day. Design an algorithm to calculate the maximum profit you can make. You can make as many trades (buying and selling a stock multiple times) as possible.

Note: You can’t participate in more than one transaction at a time (you must sell your previous shares before buying again).

Source: LeetCode

Example 1:

Input: [7,1,5,3,6,4] Output: 7 Explanation: If you buy on day 2 (stock price = 1) and sell on day 3 (stock price = 5), the exchange will make a profit = 5-1 = 4. 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

Example 2:

Input: [1,2,3,4,5] Output: 4 Explanation: If you buy on day 1 (stock price = 1) and sell on day 5 (stock price = 5), the exchange will make a profit = 5-1 = 4. Note that you can't buy stocks on day 1 and day 2 and then sell them later. Because you're doing multiple trades at once, you have to sell your shares before you can buy them again.Copy the code

Example 3:

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

Tip:

  • 1 <= prices.length <= 3 * 10 ^ 4
  • 0 <= prices[i] <= 10 ^ 4

Thought analysis

In order for a stock to make the maximum profit, the selling price must be greater than the buying price (buy > sell), and the problem states that only one stock can be bought and sold. In this question, I adopted the idea of greedy algorithm to determine the maximum profit of stocks.

How to determine the maximum profit of the stock? An 🌰

[1,2,3,4,2,6,1,2,3] maximum profit process (in the case of one trade only)?

Your subconscious approach might be to record the last number compared to the first number to record the maximum profit maxProfit, which is certainly true in this case.

So how do you think about maximum profit when you buy and sell multiple times?

Actually the profit process of the stock is split into such 1 => 2, 2 => 3, 3 => 4,2 => 6,1 => 2, 2 => 3. MaxProfit = 9. We can divide the process of obtaining the maximum profit into the process of profit accumulation one by one, and add them together to obtain the maximum profit. So every time we have a profit or a loss we can say prices[I] -prices[i-1].

AC code

int maxProfit(int* prices, int pricesSize){
    int max = 0;
    for(int i=1; i<pricesSize; i++)
    {
        if(prices[i]-prices[i- 1] >0)
            max = max + prices[i]-prices[i- 1];
    }
    return max;
}
Copy the code

Time complexity: O(n), space complexity: O(1).

conclusion

Learning to split the process is also an important step in greedy algorithms.

The last

This is No.4 of my LeetCode flash card, and the following chapters are waiting to be updated. If you like this LeetCode post, please like 😄

This article is participating in the “Gold Digging march Campaign”, click to see the details of the campaign.