0122. Best Time to Buy and Sell Stock II

Easy | Array + DP + Greedy | 60ms (75.11%), 15.1 MB (21.82%)

❓ Problem Statement

Source: LeetCode - Best Time to Buy and Sell Stock II GitHub: Solution / Performance

You are given an array prices where prices[i] is the price of a given stock on the ith day.

Find the maximum profit you can achieve. 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 simultaneously (i.e., you must sell the stock before you buy again).

✍🏻 Constraints & Example

💡 Ideas

We can use Final State Machine to solve the series of these problems.

Note that this problem allows us to do as many transactions as you like, so for each calculation of the hold state's profit, we need to consider the previous no-hold state's profit.

• Hold state means you hold the stock.

  • Since you don't have any stocks at the beginning, the profit at this state is initialized with negative infinity.

  • The profit in this state is calculated by: previous no-hold state's profit - current stock price (= buy)

• No-Hold state means you do not hold any stocks.

  • Since you don't have any stocks at the beginning (you're initially at this state ), the profit at this state is initialized with 0.

  • The profit in this state is calculated by: previous hold state's profit + current stock price (= sell)

  • Return the profit at the no-hold state as the maximum profit since the hold state still has stock on hold.

🤖 Python3

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # (base case)
        if len(prices) == 0 or len(prices) == 1: return 0
        
        # ==================================================
        #  Array + Dynamic Programming              (FSM)  =
        # ==================================================
        # time  : O(n)
        # space : O(1)
        
        hold, noHold = float('-inf'), 0
        
        for element in prices:
            preHold, preNoHold = hold, noHold
            
            # HOLD state
            #   (1) no further action in HOLD state
            #   (2) BUY at NO-HOLD state
            hold   = max(preHold,   preNoHold - element)
            
            # NO-HOLD state
            #   (1) no further action in NO-HOLD state
            #   (2) SELL at HOLD state
            noHold = max(preNoHold, preHold   + element)
        
        # (HOLD state does not have MAX profit)
        return noHold

🤖 Java