LeetCode //C - 188. Best Time to Buy and Sell Stock IV

188. 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^{th}$ 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).
 

Example 1:

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.

Example 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.

Constraints:

• 1 <= k <= 100
• 1 <= prices.length <= 1000
• 0 <= prices[i] <= 1000

From: LeetCode
Link: 188. Best Time to Buy and Sell Stock IV

Solution:

Ideas：

This function first handles a special case where k is large enough that the problem effectively becomes “make as many transactions as you want.” In that case, the best strategy is to buy and sell on every upswing. For smaller values of k, it uses dynamic programming. The array dp[i][j] represents the maximum profit from up to i transactions by the jth day. The key part of the algorithm is to keep track of the maximum difference between the current day’s price and the best profit from one fewer transaction on all previous days. This allows the algorithm to effectively decide when the optimal time to buy and sell is, for each transaction count up to k.

Code:

int maxProfit(int k, int* prices, int pricesSize) {
   
    if (pricesSize == 0) return 0;

    // When k is very large, the problem becomes the same as Best Time to Buy and Sell Stock II
    if (k >= pricesSize / 2) {
   
        int profit = 0;
        for (int i = 1; i < pricesSize; i++) {
   
            if (prices[i] > prices[i - 1]) {
   
                profit += prices[i] - prices[i - 1];
            }
        }
        return profit;
    }

    // dp array to store the maximum profit at each transaction and day
    int **dp = (int **)malloc((k + 1) * sizeof(int *));
    for (int i = 0; i <= k; i++) {
   
        dp[i] = (int *)malloc(pricesSize * sizeof(int));
    }

    for (int i = 0; i <= k; i++) {
   
        int maxDiff = INT_MIN;
        for (int j = 0; j < pricesSize; j++) {
   
            if (i == 0 || j == 0) {
   
                dp[i][j] = 0;
            } else {
   
                maxDiff = maxDiff > dp[i - 1][j - 1] - prices[j - 1] ? maxDiff : dp[i - 1][j - 1] - prices[j - 1];
                dp[i][j] = dp[i][j - 1] > prices[j] + maxDiff ? dp[i][j - 1] : prices[j] + maxDiff;
            }
        }
    }

    int result = dp[k][pricesSize - 1];

    // Free the allocated memory
    for (int i = 0; i <= k; i++) {
   
        free(dp[i]);
    }
    free(dp);

    return result;
}