The Best Time to Buy and Sell Stock IV problem is a dynamic programming challenge where we need to find the maximum profit achievable from at most k transactions in a given sequence of stock prices.

Problem Analysis

Given an array representing stock prices on different days and an integer k representing the maximum number of transactions allowed, we need to determine the maximum profit that can be achieved. Each transaction consists of buying followed by selling, and you cannot engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

3D Dynamic Programming Solution

The first approach uses a 3D DP table where dimensions represent days, number of transactinos, and holding state (0 for not holding, 1 for holding). This solution tracks the maximum profit at each day for each possible transaction count and holding state.

public int maxProfit(int maxTransactions, int[] stockPrices) {
    if (stockPrices.length == 0) {
        return 0;
    }
    
    int n = stockPrices.length;
    int[][][] profitTable = new int[n][maxTransactions + 1][2];
    
    // Initialize the DP table
    for (int t = 0; t <= maxTransactions; t++) {
        profitTable[0][t][1] = -stockPrices[0];
    }
    
    for (int day = 1; day < n; day++) {
        for (int t = 1; t <= maxTransactions; t++) {
            // 0 means not holding a stock (selling)
            profitTable[day][t][0] = Math.max(profitTable[day-1][t][0], profitTable[day-1][t][1] + stockPrices[day]);
            // 1 means holding a stock (buying)
            profitTable[day][t][1] = Math.max(profitTable[day-1][t][1], profitTable[day-1][t-1][0] - stockPrices[day]);
        }
    }
    
    return profitTable[n - 1][maxTransactions][0];
}

2D Dynamic Programming Solution

This approach optimizes space by using a 2D DP table where we represent each transaction's buy and sell states as separate columns. Odd indices represent buying states, and even indices represent selling states.

public int maxProfit(int maxTransactions, int[] stockPrices) {
    if (stockPrices.length == 0) {
        return 0;
    }
    
    int n = stockPrices.length;
    int[][] profitTable = new int[n][maxTransactions * 2 + 1];
    
    // Initialize the DP table
    for (int i = 1; i < maxTransactions * 2; i += 2) {
        profitTable[0][i] = -stockPrices[0];
    }
    
    for (int day = 1; day < n; day++) {
        for (int j = 0; j < maxTransactions * 2 - 1; j += 2) {
            profitTable[day][j+1] = Math.max(profitTable[day-1][j+1], profitTable[day-1][j] - stockPrices[day]);
            profitTable[day][j+2] = Math.max(profitTable[day-1][j+2], profitTable[day-1][j+1] + stockPrices[day]);
        }
    }
    
    return profitTable[n-1][maxTransactions * 2];
}

1D Dynamic Programming Solution

The most space-efficient approach uses a 1D array to track the states of all transactions. This solution further optimizes space by recognizing that we only need the results from the previous day to calculate the current day's results.

public int maxProfit(int maxTransactions, int[] stockPrices) {
    int n = stockPrices.length;
    if (n == 0 || maxTransactions == 0) {
        return 0;
    }
    
    int[] states = new int[2 * maxTransactions];
    
    // Initialize the states array
    for (int i = 0; i < states.length / 2; i++) {
        states[i * 2] = -stockPrices[0];
    }
    
    for (int day = 1; day <= stockPrices.length; day++) {
        states[0] = Math.max(states[0], -stockPrices[day-1]);
        states[1] = Math.max(states[1], states[0] + stockPrices[day-1]);
        
        for (int j = 2; j < states.length; j += 2) {
            states[j] = Math.max(states[j], states[j-1] - stockPrices[day-1]);
            states[j+1] = Math.max(states[j+1], states[j] + stockPrices[day-1]);
        }
    }
    
    return states[states.length - 1];
}

Each approach provides the same result but with different space complexities. The 3D solution has O(n×k) space complexity, the 2D solution reduces it to O(n×k) as well but with a smaller constant factor, and the 1D solution further optimizes it to O(k) space complexity.