Devin's Blog

Best Time To Buy And Sell Stock II

2 min read

Intuition

  • You know that you don’t want to buy then sell at a higher price.
  • You know that you always want to sell at a lower price, and never hold if you can sell
  • Simplifying this, you know that as long as its going up, you should hold, and as long as it is going down, you shouldn’t buy.
  • As soon as it starts going up, by right then and there. As soon as it starts going down, sell right there.

Complexity

Runtime

Space

Code

Simplified

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        res = 0
        for i in range(1, len(prices)):
            # As long as its going up, add each such segment
            if prices[i] > prices[i - 1]:
                res += prices[i] - prices[i - 1]
        return res
  • Instead of calculating the start and stop points, just add each point as long as its going up.

Greedy

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        prev_idx = -1
        res = 0
 
        for i in range(n - 1):
            # Haven't bought and beginning to go upward
            if prev_idx == -1 and prices[i + 1] > prices[i]:
                prev_idx = i
            
            # Bought already and beginning to go downward
            if prev_idx != -1 and prices[i + 1] < prices[i]:
                res += prices[i] - prices[prev_idx]
                prev_idx = -1
        
        if prev_idx != -1:
            res += prices[-1] - prices[prev_idx]
 
        return res

Memory Limit Exceeded

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
 
        @cache
        def r(i, bought_price):
            if i >= n:
                return 0
            
            # Haven't bought yet
            if bought_price == -1:
                # Buy or don't buy
                return max(r(i + 1, prices[i]), r(i + 1, -1))
 
            # Sell or hold
            profit = prices[i] - bought_price
            return max(profit + r(i + 1, -1), r(i + 1, bought_price))
 
        return r(0, -1)

Notes

Cards

START Basic Front: Best Time To Buy And Sell Stock II Back: Buy when it starts going up, and sell right before it starts going down END

References

Graph View