0188. Best Time to Buy and Sell Stock IV

Hard | Array + DP | 76 ms (96.01%), 14.1 MB (98.32%)

❓ Problem Statement

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

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

Find the maximum profit you can achieve. You may complete at most k transactions.

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

✍🏻 Constraints & Example

Constraints:

• 0 <= k <= 100

• 0 <= prices.length <= 1000

• 0 <= prices[i] <= 1000

Input: k = 2, prices = [2,4,1]
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

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

💡 Ideas

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

Note that this problem limits us to have at most two transactions, so we need to maintain an array with the size "T+1" (one for day 0 initialization) to record MAX profit among one or two transactions.

Keep in mind that a complete transaction means "Buy + Sell". In other words, buying new stock equals creating a new transaction. Thus, when we calculate the hold state's profit with i transactions, for buying stock, we need to take the no-hold state's profit with "i-1" transaction.

• 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's profit w/ 'i-1' transactions - cur. stock price

• 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) = hold state's profit w/ 'i' transactions + cur. stock price

  • 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, k: int, prices: List[int]) -> int:
        # (base case)
        if len(prices) == 0 or len(prices) == 1: return 0

        # ==================================================
        #  Array + Dynamic Programming              (FSM)  =
        # ==================================================
        # time  : O(nk)
        # space : O(k)
        
        # '+1' for day 0 initialization
        T = k + 1
        hold, noHold = [float('-inf')] * T, [0] * T
        
        for price in prices:
            for i in range(1, T):
                prevHold, prevNoHold = hold[i], noHold[i]
                
                hold[i]   = max(prevHold,   noHold[i-1] - price)
                noHold[i] = max(prevNoHold, prevHold    + price)
                
        return noHold[-1]

​ 🤖 Java

class Solution {
    /**
     * @time  : O(nk)
     * @space : O(k)

    public int maxProfit(int k, int[] prices) {
        /* base case */
        if(prices.length == 0 || prices.length == 1) return 0;
        
        int T = k + 1;
        
        int[] hold = new int[T], noHold = new int[T];
        Arrays.fill(hold,   Integer.MIN_VALUE);
        Arrays.fill(noHold, 0);
        
        for(int price: prices) {
            for(int i=1 ; i<T ; i++) {
                int preHold = hold[i], preNoHold = noHold[i];
                
                hold[i]   = Math.max(preHold,   noHold[i-1] - price);
                noHold[i] = Math.max(preNoHold, preHold     + price);
            }
        }
        
        return noHold[T - 1];
    }
}