Best Time to Buy and Sell Stock IV

You are given an integer array prices where prices[i] is the price of a given stock on the i<sup>th</sup> 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).

For example:

• k = 2, prices = [2,4,1] should return 2 (Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2).
• k = 2, prices = [3,2,6,5,0,3] should return 7 (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).

## Maximum Profit with k Transactions

This problem asks us to find the maximum profit that can be achieved by completing at most `k` transactions in a given array of stock prices.

### 1. Brute Force Solution

A brute-force approach would involve exploring all possible combinations of buy and sell transactions within the given `k` limit. This would involve recursion and exploring different paths, which is highly inefficient.

```python
def max_profit_brute_force(k, prices):
    def solve(index, transactions_left, holding):
        if index == len(prices) or transactions_left == 0:
            return 0

        # Skip the current day
        skip = solve(index + 1, transactions_left, holding)

        if holding:
            # Sell stock
            sell = prices[index] + solve(index + 1, transactions_left - 1, False)
            return max(skip, sell)
        else:
            # Buy stock
            buy = -prices[index] + solve(index + 1, transactions_left, True)
            return max(skip, buy)

    return solve(0, 2 * k, False) # 2*k because each transaction consists of buy and sell

2. Optimal Solution: Dynamic Programming

The optimal solution involves using dynamic programming to store and reuse intermediate results. We can create a DP table where dp[i][j] represents the maximum profit achievable with i transactions up to day j. We can optimize space complexity by using only 2 rows for current and previous day.

def max_profit(k, prices):
    n = len(prices)

    # Edge case: If no prices or no transactions, return 0
    if n == 0 or k == 0:
        return 0

    # If k is large enough to do infinite transactions, use a simpler approach
    if k >= n // 2:
        profit = 0
        for i in range(1, n):
            diff = prices[i] - prices[i - 1]
            if diff > 0:
                profit += diff
        return profit

    # Initialize DP table
    dp = [[0] * n for _ in range(k + 1)]

    # Iterate through transactions
    for i in range(1, k + 1):
        max_diff = -float('inf')
        # Iterate through prices
        for j in range(1, n):
            dp[i][j] = dp[i][j - 1]
            max_diff = max(max_diff, dp[i - 1][j - 1] - prices[j - 1])
            dp[i][j] = max(dp[i][j], prices[j] + max_diff)

    return dp[k][n - 1]

3. Big(O) Run-time Analysis

• Time Complexity: O(k * n), where k is the number of transactions allowed and n is the number of days (prices).
  • The outer loop iterates k times.
  • The inner loop iterates n times.
  • The max_diff calculation takes constant time.

4. Big(O) Space Usage Analysis

• Space Complexity: O(k * n)
  • The DP table dp has dimensions (k + 1) x n.

5. Edge Cases and Handling

• Empty Prices Array: If the prices array is empty, return 0 because no profit can be made.
• Zero Transactions: If k is 0, return 0 because no transactions are allowed.
• Large k: If k is greater than or equal to n/2, we can simply sum up all the positive differences between consecutive days because effectively any number of transactions is allowed. This simplifies the problem and avoids unnecessary computation.
• Negative Prices: The problem statement mentions that prices are non-negative, but if there were negative prices, the algorithm would still function correctly because it maximizes profit by considering buying and selling at different prices.

Example Usage

k = 2
prices = [3, 2, 6, 5, 0, 3]
print(max_profit(k, prices))  # Output: 7