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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Best Time to Buy and Sell Stock IV

Difficulty: Hard

Problem Description

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: i.e. you may buy at most k times and sell at most k times. Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Key Insights

  • The problem involves calculating profits from stock transactions with a limited number of transactions (k).
  • Dynamic Programming is suitable due to overlapping subproblems and optimal substructure.
  • The solution requires tracking profits for each transaction and each day, necessitating a two-dimensional DP table.
  • Edge cases include when k exceeds half the number of days, where the solution simplifies to unlimited transactions.

Space and Time Complexity

Time Complexity: O(k * n), where n is the number of days (length of the prices array).
Space Complexity: O(k), as we can optimize the DP storage to only keep track of the last transaction.

Solution

The solution utilizes a dynamic programming approach, where we maintain a DP array that tracks the maximum profit achievable with up to k transactions up to each day. The algorithm iteratively updates profits based on the best prior profits and the current day's prices.

  1. Initialize a DP array of size (k+1) with zeros.
  2. Iterate through each day and each transaction, updating the maximum profit possible by considering the best prior profits and the differences in prices.
  3. Return the maximum profit from the last transaction after processing all days.

Code Solutions

def maxProfit(k, prices):
    if not prices or k == 0:
        return 0
    n = len(prices)
    # If k is greater than half of days, we can treat it as unlimited transactions
    if k >= n // 2:
        return sum(max(prices[i + 1] - prices[i], 0) for i in range(n - 1))

    # DP table
    dp = [[0] * n for _ in range(k + 1)]
    
    for i in range(1, k + 1):
        max_diff = -prices[0]
        for j in range(1, n):
            dp[i][j] = max(dp[i][j - 1], prices[j] + max_diff)
            max_diff = max(max_diff, dp[i - 1][j] - prices[j])
    
    return dp[k][n - 1]
← Back to All Questions