188. Best Time to Buy and Sell Stock IV

  • 24.0%

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

Say you have an array for which the ith 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).


java


https://discuss.leetcode.com/topic/8984/a-concise-dp-solution-in-java

A Concise DP Solution in Java

The general idea is DP, while I had to add a “quickSolve” function to tackle some corner cases to avoid TLE.

DP: t(i,j) is the max profit for up to i transactions by time j (0<=i<=K, 0<=j<=T).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int maxProfit(int k, int[] prices) {
int len = prices.length;
if (k >= len / 2) return quickSolve(prices);

int[][] t = new int[k + 1][len];
for (int i = 1; i <= k; i++) {
int tmpMax = -prices[0];
for (int j = 1; j < len; j++) {
t[i][j] = Math.max(t[i][j - 1], prices[j] + tmpMax);
tmpMax = Math.max(tmpMax, t[i - 1][j - 1] - prices[j]);
}
}
return t[k][len - 1];
}


private int quickSolve(int[] prices) {
int len = prices.length, profit = 0;
for (int i = 1; i < len; i++)
// as long as there is a price gap, we gain a profit.
if (prices[i] > prices[i - 1]) profit += prices[i] - prices[i - 1];
return profit;
}

https://discuss.leetcode.com/topic/26169/clean-java-dp-solution-with-comment

Clean Java DP solution with comment

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
/**
* dp[i, j] represents the max profit up until prices[j] using at most i transactions.
* dp[i, j] = max(dp[i, j-1], prices[j] - prices[jj] + dp[i-1, jj]) { jj in range of [0, j-1] }
* = max(dp[i, j-1], prices[j] + max(dp[i-1, jj] - prices[jj]))
* dp[0, j] = 0; 0 transactions makes 0 profit
* dp[i, 0] = 0; if there is only one price data point you can't make any transaction.
*/

public int maxProfit(int k, int[] prices) {
int n = prices.length;
if (n <= 1)
return 0;

//if k >= n/2, then you can make maximum number of transactions.
if (k >= n/2) {
int maxPro = 0;
for (int i = 1; i < n; i++) {
if (prices[i] > prices[i-1])
maxPro += prices[i] - prices[i-1];
}
return maxPro;
}

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

https://discuss.leetcode.com/topic/24079/easy-understanding-and-can-be-easily-modified-to-different-situations-java-solution

Easy understanding and can be easily modified to different situations Java Solution

The basic idea is to create two tables. hold and unhold.

hold[i][j] means the maximum profit with at most j transaction for 0 to i-th day. hold means you have a stock in your hand.

unhold[i][j] means the maximum profit with at most j transaction for 0 to i-th day. unhold means you don’t have a stock in your hand.

The equation is

1
2
3
hold[i][j] = Math.max(unhold[i-1][j]-prices[i],hold[i-1][j]);

unhold[i][j] = Math.max(hold[i-1][j-1]+prices[i],unhold[i-1][j]);

when you sell your stock this is a transaction but when you buy a stock, it is not considered as a full transaction. so this is why the two equation look a little different.

And we have to initiate hold table when k = 0.

When the situation is you can not buy a new stock at the same day when you sell it. For example you can only buy a new stock after one day you sell it. The same idea. Another situation is when you have to pay a transaction fee for each transaction, just make a modification when you sell it, So just change the unhold equation a little.

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
public class Solution {
//hold[i][k] ith day k transaction have stock and maximum profit
//unhold[i][k] ith day k transaction do not have stock at hand and maximum profit
public int maxProfit(int k, int[] prices) {
if(k>prices.length/2) return maxP(prices);
int[][] hold = new int[prices.length][k+1];
int[][] unhold = new int[prices.length][k+1];
hold[0][0] = -prices[0];
for(int i=1;i<prices.length;i++) hold[i][0] = Math.max(hold[i-1][0],-prices[i]);
for(int j=1;j<=k;j++) hold[0][j] = -prices[0];
for(int i=1;i<prices.length;i++){
for(int j=1;j<=k;j++){
hold[i][j] = Math.max(unhold[i-1][j]-prices[i],hold[i-1][j]);
unhold[i][j] = Math.max(hold[i-1][j-1]+prices[i],unhold[i-1][j]);
}
}
return Math.max(hold[prices.length-1][k],unhold[prices.length-1][k]);
}
public int maxP(int[] prices){
int res =0;
for(int i=0;i<prices.length;i++){
if(i>0 && prices[i] > prices[i-1]){
res += prices[i]-prices[i-1];
}
}
return res;
}
}

cpp


https://discuss.leetcode.com/topic/9522/c-solution-with-o-n-klgn-time-using-max-heap-and-stack

C++ Solution with O(n + klgn) time using Max Heap and Stack

We can find all adjacent valley/peak pairs and calculate the profits easily. Instead of accumulating all these profits like Buy&Sell Stock II, we need the highest k ones.

The key point is when there are two v/p pairs (v1, p1) and (v2, p2), satisfying v1 <= v2 and p1 <= p2, we can either make one transaction at [v1, p2], or make two at both [v1, p1] and [v2, p2]. The trick is to treat [v1, p2] as the first transaction, and [v2, p1] as the second. Then we can guarantee the right max profits in both situations, p2 - v1 for one transaction and p1 - v1 + p2 - v2 for two.

Finding all v/p pairs and calculating the profits takes O(n) since there are up to n/2 such pairs. And extracting k maximums from the heap consumes another O(klgn).

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
class Solution {
public:
int maxProfit(int k, vector<int> &prices) {
int n = (int)prices.size(), ret = 0, v, p = 0;
priority_queue<int> profits;
stack<pair<int, int> > vp_pairs;
while (p < n) {
// find next valley/peak pair
for (v = p; v < n - 1 && prices[v] >= prices[v+1]; v++);
for (p = v + 1; p < n && prices[p] >= prices[p-1]; p++);
// save profit of 1 transaction at last v/p pair, if current v is lower than last v
while (!vp_pairs.empty() && prices[v] < prices[vp_pairs.top().first]) {
profits.push(prices[vp_pairs.top().second-1] - prices[vp_pairs.top().first]);
vp_pairs.pop();
}
// save profit difference between 1 transaction (last v and current p) and 2 transactions (last v/p + current v/p),
// if current v is higher than last v and current p is higher than last p
while (!vp_pairs.empty() && prices[p-1] >= prices[vp_pairs.top().second-1]) {
profits.push(prices[vp_pairs.top().second-1] - prices[v]);
v = vp_pairs.top().first;
vp_pairs.pop();
}
vp_pairs.push(pair<int, int>(v, p));
}
// save profits of the rest v/p pairs
while (!vp_pairs.empty()) {
profits.push(prices[vp_pairs.top().second-1] - prices[vp_pairs.top().first]);
vp_pairs.pop();
}
// sum up first k highest profits
for (int i = 0; i < k && !profits.empty(); i++) {
ret += profits.top();
profits.pop();
}
return ret;
}
};

https://discuss.leetcode.com/topic/12250/share-my-c-dp-solution-with-o-kn-time-o-k-space-10ms

Share my C++ DP solution with O(kn) time O(k) space, 10ms

This is my DP 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
class Solution {

public:
int maxProfit(int k, vector<int> &prices) {
int len = prices.size();
if (len<2) return 0;
if (k>len/2){ // simple case
int ans = 0;
for (int i=1; i<len; ++i){
ans += max(prices[i] - prices[i-1],0);
}
return ans;
}
int hold[k+1];
int rele[k+1];
for (int i=0;i<=k;++i){
hold[i] = INT_MIN;
rele[i] = 0;
}
int cur;
for (int i=0; i<len; ++i){
cur = prices[i];
for(int j=k; j>0; --j){
rele[j] = max(rele[j],hold[j] + cur);
hold[j] = max(hold[j],rele[j-1] - cur);
}
}
return rele[k];
}
};

Inspired by weijiac in Best Time to Buy and Sell Stock III

https://leetcode.com/discuss/18330/is-it-best-solution-with-o-n-o-1


https://discuss.leetcode.com/topic/30242/o-n-time-8ms-accepted-solution-with-detailed-explanation-c

O(n)-time 8ms Accepted Solution with Detailed Explanation (C++)

The idea of this thread was originally proposed by @yishiluo in

https://leetcode.com/discuss/26745/c-solution-with-o-n-klgn-time-using-max-heap-and-stack

General idea:

We use the term “valley” to denote a local minimum index of prices, and the term “peak” to denote a local maximum index of prices. Let (v1, p1) and (v2, p2) denote two successive valley-peak pairs of the prices, respectively. Consider the two cases:

  • Case 1: prices[v1] <= prices[v2] and prices[p1] <= prices[p2]. In this case, if we can conduct one transaction, we will use (v1, p2). If we can conduct two transactions, we will use (v1, p1) and (v2, p2). Equivalently, we can consider (v1, p2) as one transaction opportunity, and (v2, p1) as another transaction opportunity. The key idea is that these two original valley-peak pairs provide two transaction opportunities: (v1, p2) and (v2, p1).

  • Case 2: prices[v1] >= prices[v2] or prices[p1] >= prices[p2]. In this case, if we can conduct one transaction, we will use either (v1, p1) or (v2, p2). If we can conduct two transactions, we will use both (v1, p1) and (v2, p2). That is, these two valley-peak pairs provides two transaction opportunities: (v1, p1) and (v2, p2).

The algorithm consists of two steps:

  • Step 1: Find all transaction opportunities and record their profits. We use a stack vps to store the valley-peak pairs of the stock prices, wherein the valley value is sorted in ascending order. (The valley value at the top of the stack is the largest.) The profit of all transaction opportunities are recorded in the vector profits. The time complexity of this step is O(n).

  • Step 2: Find the k most profitable transaction opportunities. The maximum profit we can get is the summation of the k opportunity. The time complexity of this step is O(n), too.

Overall complexity:

  • Time: O(n)

  • Space: worse-case O(n)

C++ code (Accepted 8ms)

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
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {

// Step 1: Find out all profit opportunities
vector<int> profits;
stack<pair<int, int>> vps; // valley-peak pairs

int v;
int p = -1;
for (;;) {
// find next valley-peak pair
for (v = p+1; (v+1 < prices.size()) && (prices[v] >= prices[v+1]); ++v);
for (p = v ; (p+1 < prices.size()) && (prices[p] <= prices[p+1]); ++p);

if (v == p) { // v==p means that both v and p reach the end of the array
break;
}

// Consider two transactions (v1, p1) (back of the stack) and (v2, p2) (the new-found).
// If prices[v1] >= prices[v2],
// it is meaningless to combine the two transactions.
// Save of profit of (v1, p1), and pop it out of the record.
while ((!vps.empty()) && (prices[v] <= prices[vps.top().first])) {
profits.push_back(prices[vps.top().second] - prices[vps.top().first]);
vps.pop();
}

// If prices[v1]<prices[v2] and prices[p1]<prices[p2],
// then it is meaningful to combine the two transactions
// update (v1, p1) to (v1, p2), and save the profit of (v2, p1)
while ((!vps.empty()) && (prices[p] >= prices[vps.top().second])) {
profits.push_back(prices[vps.top().second] - prices[v]);
v = vps.top().first;
vps.pop();
}

// save the new-found valley-peak pair
vps.emplace(v, p);
}

// save all remaining profits
while (!vps.empty()) {
profits.push_back(prices[vps.top().second] - prices[vps.top().first]);
vps.pop();
}

// Step 2: Calculate the k highest profits
int ret;
if (profits.size() <= k) {
ret = accumulate(profits.begin(), profits.end(), 0);
} else {
nth_element(profits.begin(), profits.end() - k, profits.end());
ret = accumulate(profits.end() - k, profits.end(), 0);
}
return ret;
}
};

python


https://discuss.leetcode.com/topic/22245/well-explained-python-dp-with-comments

Well explained Python DP with comments

I think the general idea has been thoroughly explained by other brilliant leetcoders. All of the solutions are beautiful and concise. However, most of the them don’t look obvious to me, so I wrote this and hope it looks more straight forward.
It’s O(kn), apparently not optimal. I name the key variables as local profit and global profit to make things much understandable (well, at least , to me). Performance is not too bad though.

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
def maxProfit4(self, k, prices):
n = len(prices)
if n < 2:
return 0
# k is big enougth to cover all ramps.
if k >= n / 2:
return sum(i - j
for i, j in zip(prices[1:], prices[:-1]) if i - j > 0)
globalMax = [[0] * n for _ in xrange(k + 1)]
for i in xrange(1, k + 1):
# The max profit with i transations and selling stock on day j.
localMax = [0] * n
for j in xrange(1, n):
profit = prices[j] - prices[j - 1]
localMax[j] = max(
# We have made max profit with (i - 1) transations in
# (j - 1) days.
# For the last transation, we buy stock on day (j - 1)
# and sell it on day j.
globalMax[i - 1][j - 1] + profit,
# We have made max profit with (i - 1) transations in
# (j - 1) days.
# For the last transation, we buy stock on day j and
# sell it on the same day, so we have 0 profit, apparently
# we do not have to add it.
globalMax[i - 1][j - 1], # + 0,
# We have made profit in (j - 1) days.
# We want to cancel the day (j - 1) sale and sell it on
# day j.
localMax[j - 1] + profit)
globalMax[i][j] = max(globalMax[i][j - 1], localMax[j])
return globalMax[k][-1]

谢谢你,可爱的朋友。