

Multiple States VII

Description

Say you have an array for which the i-th element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete at most k transactions.

Question Link

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

Example I

Input: [2,4,1], k = 2
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

Example II:

Input: [3,2,6,5,0,3], k = 2
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.

Questions

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

Transform Function

               /
               |    dp[i][j - 1]
dp[i][j] = max |
               |    prices[j] - prices[m] + dp[i - 1][m]
               \

Template I

// Submission Result: Memory Limit Exceeded
class Solution {
    public int maxProfit(int k, int[] prices) {
        if(k == 0 || prices.length == 0) return 0; 
        int m = k, n = prices.length;
        int[][] dp = new int[m + 1][n];

        for(int i = 1; i <= m; i++) {
            for(int j = 1; j < n; j++) {
                for(int s = 0; s < j; s++) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][s] + prices[j] - prices[s]);
                }
                dp[i][j] = Math.max(dp[i][j], dp[i][j - 1]);
            }
        }
        return dp[m][n - 1];
    }
}

Optimized

i = 1, j = 3
dp[1][0] - prices[0] + prices[3]
dp[1][1] - prices[1] + prices[3]
dp[1][2] - prices[2] + prices[3]

Template II

class Solution {
    public int maxProfit(int k, int[] prices) {
        if(k == 0 || prices.length == 0) return 0; 
        if(k >= prices.length / 2) return helper(prices);
        int n = prices.length;
        int[] dp = new int[n];
        int[] prev = new int[n];

        for(int i = 1; i <= k; i++) {
            int maxDiff = -prices[0];
            for(int j = 1; j < n; j++) {
                dp[j] = Math.max(dp[j - 1], maxDiff + prices[j]);
                maxDiff = Math.max(maxDiff, prev[j] - prices[j]);
            }
            prev = Arrays.copyOf(dp, dp.length);
        }
        return dp[n - 1];
    }

    int helper(int[] prices) {
        int res = 0;
        for(int i = 1; i < prices.length; i++) {
            if(prices[i] > prices[i - 1]) res += prices[i] - prices[i - 1];
        }
        return res;
    }
}

Optimized

transaction on i th day

dp[i] = max{dp[i - 1][no tansaction] + sell, dp[i - 1][do transaction] + buy}

for (int i = 0; i < n; i++)
{
    dp[i][no transaction] = max(dp[i - 1][do transaction] + buy, dp[i - 1][no tansaction] + hold );
    dp[i][do transaction] = max(dp[i - 1][no transaction] + sell, dp[i - 1][do transaction] + hold );
}
return dp[n - 1][do transaction];

for (int i = 0; i < n; i++)
{
    for (int j = 0; j <= k; j++)
    {
      dp[i][no transaction][j] = max {dp[i - 1][do transaction][j - 1] + buy, dp[i - 1][no transaction][j] + hold };
      dp[i][do transaction][j] = max {dp[i - 1][no transaction][j] + sell, dp[i - 1][do transaction][j] + hold  };
    }
}
return dp[n-1][do transaction];

hold[i][j] = max {sold[i - 1][j - 1] + buy, hold[i - 1][j]}
sold[i][j] = max {hold[i - 1][j] + sell, sold[i - 1][j]}

Template III

class Solution {
    public int maxProfit(int k, int[] prices) {
        if(k == 0 || prices.length == 0) return 0; 
        if(k >= prices.length / 2) return helper(prices);
        int n = prices.length;
        int[][] hold = new int[n][k + 1];
        int[][] sold = new int[n][k + 1];

        for(int i = 1; i < n; i++) {
            int diff = prices[i] - prices[i - 1];
            for(int j = 1; j <= k; j++) {
                hold[i][j] = Math.max(sold[i - 1][j - 1] + diff, hold[i - 1][j] + diff);
                sold[i][j] = Math.max(hold[i][j], sold[i - 1][j]);
            }
        }
        return sold[n - 1][k];
    }

    int helper(int[] prices) {
        int res = 0;
        for(int i = 1; i < prices.length; i++) {
            if(prices[i] > prices[i - 1]) res += prices[i] - prices[i - 1];
        }
        return res;
    }
}