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

Constraints:

• 1 <= prices.length <= 3 * 10^4

• 0 <= prices[i] <= 10^4

Input: prices = [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.

Input: prices = [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.

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

💡 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

class Solution {
    /**
     * @time  : O(n)
     * @space : O(1)
     * 
     * Greedy Method
     */
    
    public int maxProfit(int[] prices) {
        /* base case */
        if(prices.length == 1) return 0;
        
        int profit = 0;
        
        for(int i=1 ; i<prices.length ; i++) {
            int tmpProfit = prices[i] - prices[i-1];
            if(tmpProfit > 0) profit += tmpProfit;
        }
        
        return profit;
    }
}