We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Best Time to Buy and Sell Stock IV

Number: 188

Difficulty: Hard

Paid? No

Companies: Amazon, Google, Meta, Goldman Sachs, Microsoft, TikTok, Apple, Citadel, Adobe, Nvidia

Problem Description

Given an array of stock prices where prices[i] is the price on the iᵗʰ day and an integer k, determine the maximum profit achievable with at most k transactions (a transaction is defined as one buy and one sell). Note that you cannot hold more than one stock at a time (i.e., you must sell before buying again).

Key Insights

  • For a high value of k (k >= n/2 where n is the number of days), the problem reduces to the unlimited transactions case.
  • When k is small, a dynamic programming approach is necessary to track the optimal profit at each transaction and day.
  • Use a DP recurrence: dp[t][i] = max(dp[t][i-1], prices[i] + maxDiff), where maxDiff is updated as max(maxDiff, dp[t-1][i] - prices[i]).
  • The idea is to iteratively build the solution for each transaction, using previously computed results efficiently.

Space and Time Complexity

Time Complexity: O(k * n) where n is the number of days. Space Complexity: O(k * n) for the DP table (can be optimized to O(n) per transaction if needed).

Solution

We use a dynamic programming solution. First, check if k is large enough to allow unlimited transactions. If yes, simply sum up all positive differences between consecutive days. Otherwise, create a 2D DP table where dp[t][i] represents the maximum profit using at most t transactions until day i. For each transaction from 1 to k and for each day we maintain a variable maxDiff representing the maximum value of (dp[t-1][j] - prices[j]) for j from 0 to the current day. This helps to update the dp state for a transaction with a sell on the current day using the optimal previous transaction state.

Code Solutions

# Python solution for Best Time to Buy and Sell Stock IV

def maxProfit(k, prices):
    # Edge case: if there are no prices, no profit can be made.
    n = len(prices)
    if n == 0 or k == 0:
        return 0
    
    # If k is large enough, perform as many transactions as possible.
    if k >= n // 2:
        total_profit = 0
        for i in range(1, n):
            # Add profit if today's price is higher than yesterday's.
            if prices[i] > prices[i - 1]:
                total_profit += prices[i] - prices[i - 1]
        return total_profit
    
    # Initialize DP table: dp[t][i] is the max profit for at most t transactions until day i.
    dp = [[0] * n for _ in range(k + 1)]
    
    # Fill the DP table for each transaction from 1 to k.
    for t in range(1, k + 1):
        maxDiff = -prices[0]  # Initialize maxDiff as maximum value of dp[t-1][0] - prices[0].
        for i in range(1, n):
            # Either do not trade on day i or sell on day i using best buy option.
            dp[t][i] = max(dp[t][i - 1], prices[i] + maxDiff)
            # Update maxDiff to incorporate the profit from previous transaction.
            maxDiff = max(maxDiff, dp[t - 1][i] - prices[i])
    return dp[k][n - 1]

# Example usage:
print(maxProfit(2, [3,2,6,5,0,3]))  # Expected output: 7
← Back to All Questions