[Leetcode] 122. Best Time to Buy and Sell Stock II

Medium level

 

Intuition:

 

We can buy and sell any time without penalty, so it's intuitive to just loop and if the price difference is positive between two consecutive days, we assume we'll hold the stock ( or buy the stock the day before ), and sell the day before otherwise. The question also only asks for the total profit, not the date when the stocks are bought and sold. So a simple greedy algorithm  is enough to solve this.

 

My solution:

 

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0
        for idx, price in enumerate(prices):
            if idx > 0:
                prev_price = prices[idx-1]
                if price - prev_price > 0:
                    profit += price - prev_price
        return profit

 

Time complexitiy: O(n)

Space complexity: O(1)

 

Most upvoted:

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        
		# It is impossible to sell stock on first day, set -infinity as initial value for cur_hold
        cur_hold, cur_not_hold = -float('inf'), 0
        
        for stock_price in prices:
            
            prev_hold, prev_not_hold = cur_hold, cur_not_hold
            
			# either keep hold, or buy in stock today at stock price
            cur_hold = max( prev_hold, prev_not_hold - stock_price )
			
			# either keep not-hold, or sell out stock today at stock price
            cur_not_hold = max( prev_not_hold, prev_hold + stock_price )
            
        # maximum profit must be in not-hold state
        return cur_not_hold

 

Imo, this is very similar to my own solution. The author says it's a DP + iteration solution, which I guess is correct since one can assume that comparing two consecutive stock prices constitute as a subproblem.