[LeetCode] 188. Best Time to Buy and Sell Stock IV

Posted on | In

Problem

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.

Note:

You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Example 1:

1
2
3
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 2:

1
2
3
4
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.

Explanation

  1. We can use dynamic programming to solve this problem.

  2. Dynamic state is a two dimensional array dp[t][d], row is transaction and column is the day, and it represents the maximum profit can be made using at most t transaction in d day. Note, the length of the row is t+1 because we need consider zero transaction.

  3. Dynamic init is dp[0][d] (top row) all values will be zero because we are not making any transaction. dp[t][0] all (left column) will be zero because if only has one day, then we can’t make any profit for one day.

  4. Dynamic function will be taking the maximum profit of either not making any transaction on day d, which is dp[t][d-1]; another way is make transaction on day d, which the profit will be prices[d] - prices[m] + dp[t-1][m], where m will be the day we buy the stock and sell this stock on day d for the last transaction and m will be from 0 to d-1. How do we find the m? We can switch the order of prices[d] - prices[m] + dp[t-1][m] to prices[d] + (dp[t-1][m] - prices[m]), so we need to find the m that makse the maximum of dp[t-1][m] - prices[m], let’s call this maxDiff. So, we can iterate the m from 0 to d-1, and find the maximum of maxDiff. Therefore, the dynamic function is max(dp[t][d-1], prices[d] + maxDiff where maxDiff = dp[t-1][m]-prices[m] for m = 0 to d-1.

  5. Dynamic result will be the bottom right value, which is dp[t][d].

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
class Solution {
    public int maxProfit(int k, int[] prices) {
        if (prices == null || prices.length == 0 || k == 0) return 0;
        if (k >= prices.length) {
            int profit = 0;
            int min = prices[0];
            for (int i = 1; i < prices.length; i++) {
                if (prices[i-1] >= prices[i]) {
                    min = prices[i];
                } else {
                    profit += prices[i]-min;
                    min = prices[i];
                }
            }
            return profit;
        }

        int[] res = new int[prices.length];
        int[] prev = new int[prices.length];

        for (int t = 1; t <= k; t++) {
            int maxDiff = -prices[0];
            for (int d = 1; d < prices.length; d++) {
                res[d] = Math.max(res[d-1], prices[d] + maxDiff);
                maxDiff = Math.max(maxDiff, prev[d] - prices[d]);
            }
            for (int i = 0; i < res.length; i++) {
                prev[i] = res[i];
            }
        }

        return res[res.length - 1];
    }
}

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

//         for (int t = 1; t < dp.length; t++) {
//             int maxDiff = -prices[0];
//             for (int d = 1; d < dp[0].length; d++) {
//                 dp[t][d] = Math.max(dp[t][d-1], prices[d]+maxDiff);
//                 maxDiff = Math.max(maxDiff, dp[t-1][d]-prices[d]);
//             }
//         }

//         return dp[k][prices.length-1];
//     }
// }

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

//         for (int t = 1; t < dp.length; t++) {
//             for (int d = 1; d < dp[0].length; d++) {
//                 int maxVal = Integer.MIN_VALUE;
//                 for (int m = 0; m < d; m++) {
//                     maxVal = Math.max(maxVal, prices[d]+dp[t-1][m]-prices[m]);
//                 }
//                 dp[t][d] = Math.max(dp[t][d-1], maxVal);
//             }
//         }

//         return dp[k][prices.length-1];
//     }
// }