LeetCode 188. Best Time to Buy and Sell Stock IV

Question

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.

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:

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

Source: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/

Solution

To find an efficient solution for this type of problem, we need to use DP.

However, let us consider an extreme case fisrt. We are allow to make at most k transactions. If k is large enough to enable us to grab every profit, we do not have to do DP but just traverse the array once. The threshold of this k is n/2. Because a stock can rise at most n/2 times (two rises on two adjacent days can be merged into one). This is the idea of quickSolve().

For DP, the essence of DP is to solve small sub-problems first, and derive the results from these small sub-problem to larger problems. This max profit problem has two dimensions: 1. the number of days; 2. the max number of transactions allowed. So we creaste a 2D DP cache. And because deriving results from fewer days to more days is easier than changing max number of transactions, we make k+1 (more convenient than k) the first dimension and n the second dimension. Always use a variable that is easier to derive as the second dimension in 2D DP.

dp[i][j] represents the max profit of prices[:j] (inclusive) with at most i transactions. Thus, there are only two options for dp[i][j]: sell the stock on jth day or not. If sell, we need to iterate all possible cases to find the max profit. If not, dp[i][j] should be equal to dp[i][j-1].

So, we can get the following formulas for these two situations:

1. dp[i][j] = dp[i][j-1].
2. t is the date the last transaction was brought. dp[i][j] = for t: 0->j-1, max(dp[i-1][t-1]+prices[j]-prices[t]) .

This solution still has a O((n^2)*k) time complexity. The bottleneck is the second formula. However, we can further optimize it. It is equivalent to for t: 0->j-1, max(dp[i-1][t-1]-prices[t])+prices[j]. Thus, we can find the max of the second formula while iterating 0 to j-1 once.

Finally, the time complexity is optimized to O(nk).

// return the max profit without limiting the number of transactions
private int quickSolve(int[] prices) {
    int maxProfit = 0;
    for (int i = 1; i < prices.length; i++) {
        // short-term trading
        maxProfit += Math.max(0, prices[i] - prices[i - 1]);
    }
    return maxProfit;
}

// Time Complexity O(nk)
public int maxProfit(int k, int[] prices) {
    int n = prices.length;
    // if k allows us to get every profit
    if (k >= n / 2) {
        return quickSolve(prices);
    }
    // dp[i][j] is the max profit of prices[:j] (inclusive) with at most i transactions
    int[][] dp = new int[k + 1][n];
    for (int i = 1; i <= k; i++) {
        // dp[i-1][t-1]-prices[t]
        int maxTemp = -prices[0];
        for (int j = 1; j < n; j++) {
            dp[i][j] = Math.max(dp[i][j - 1], maxTemp + prices[j]);
            maxTemp = Math.max(maxTemp, dp[i - 1][j - 1] - prices[j]);
        }
    }
    return dp[k][n - 1];
}