leetcode_gym/_problems/buyAndSellStock2.md

layout, title, last_solved, category, leetcode_url, status

layout	title	last_solved	category	leetcode_url	status
page	Buy and Sell Stock 2	2020-06-02	array	https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii	Solved

Problem

{% highlight text %}

Say you have an array prices for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Example 1:

Input: [7,1,5,3,6,4] Output: 7 Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4. Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3. Example 2:

Input: [1,2,3,4,5] Output: 4 Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4. Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again. Example 3:

Input: [7,6,4,3,1] Output: 0 Explanation: In this case, no transaction is done, i.e. max profit = 0.

{% endhighlight %}

Solution

This one is actually easier than the first one (Buy and Sell Stock 1) because you're not restricted to making only one trade.

Since you can make multiple trades, you can buy and sell at every peak and valley. In that case, just sum up all the positive days and sum it up.

{% highlight python %}

def maxProfit(self, prices: List[int]) -> int:

positive_days = []

for i in range(len(prices)-1):
    
    if prices[i+1]-prices[i]>0:
        positive_days.append( prices[i+1]-prices[i] )
    
return sum(positive_days)

{% endhighlight %}

We can make it constant space by changing positive_days to a variable that we continously sum up.