123. Best Time to Buy and Sell Stock III

  • 28.6%

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

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 two transactions.

Note:

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


方法一:

微策略面试题

我的代码实现:

Oct 17, 2017

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
int maxProfit(vector<int>& prices) {
vector<int> v = {INT_MIN, 0, INT_MIN, 0};
for(auto price:prices){
v[0] = max(v[0], -price);
v[1] = max(v[1], v[0]+price);
v[2] = max(v[2], v[1]-price);
v[3] = max(v[3], v[2]+price);
}
return max(v[1], v[3]);
}
};

My C++ solution (O(N) time, O(1) space, 8ms)

It is similar to other buy/sell problems. just do DP and define an array of states to track the current maximum profits at different stages.

For example, in the below code

  • states[][0]: one buy
  • states[][1]: one buy, one sell
  • states[][2]: two buys, one sell
  • states[][3]: two buy, two sells

The states transistions occurs when buy/sell operations are executed. For example, state[][0] can move to state[][1] via one sell operation.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
int maxProfit(vector<int>& prices) {
int states[2][4] = {INT_MIN, 0, INT_MIN, 0}; // 0: 1 buy, 1: one buy/sell, 2: 2 buys/1 sell, 3, 2 buys/sells
int len = prices.size(), i, cur = 0, next =1;
for(i=0; i<len; ++i)
{
states[next][0] = max(states[cur][0], -prices[i]);
states[next][1] = max(states[cur][1], states[cur][0]+prices[i]);
states[next][2] = max(states[cur][2], states[cur][1]-prices[i]);
states[next][3] = max(states[cur][3], states[cur][2]+prices[i]);
swap(next, cur);
}
return max(states[cur][1], states[cur][3]);
}
};

方法二:

高效、简便、容易想到的方法

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
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
if(n<2) return 0;
vector<int> dp1(n, 0);
vector<int> dp2(n, 0);
int minPrice = INT_MAX;
int maxProfit1 = 0;
for(int i=0; i<n; i++){
minPrice = min(minPrice, prices[i]);
maxProfit1 = max(maxProfit1, prices[i]-minPrice);
dp1[i] = maxProfit1;
}
int maxPrice = INT_MIN;
int maxProfit2 = 0;
for(int i=n-1; i>=0; i--){
maxPrice = max(maxPrice, prices[i]);
maxProfit2 = max(maxProfit2, maxPrice-prices[i]);
dp2[i] = maxProfit2;
}
int maxProfit = 0;
for(int i=0; i<n; i++){
maxProfit = max(maxProfit, dp1[i]+dp2[i]);
}
return maxProfit;
}
};

cpp


https://discuss.leetcode.com/topic/19750/my-c-solution-o-n-time-o-1-space-8ms

My C++ solution (O(N) time, O(1) space, 8ms)

It is similar to other buy/sell problems. just do DP and define an array of states to track the current maximum profits at different stages.

For example, in the below code

  • states[][0]: one buy
  • states[][1]: one buy, one sell
  • states[][2]: two buys, one sell
  • states[][3]: two buy, two sells

The states transistions occurs when buy/sell operations are executed. For example, state[][0] can move to state[][1] via one sell operation.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
int maxProfit(vector<int>& prices) {
int states[2][4] = {INT_MIN, 0, INT_MIN, 0}; // 0: 1 buy, 1: one buy/sell, 2: 2 buys/1 sell, 3, 2 buys/sells
int len = prices.size(), i, cur = 0, next =1;
for(i=0; i<len; ++i)
{
states[next][0] = max(states[cur][0], -prices[i]);
states[next][1] = max(states[cur][1], states[cur][0]+prices[i]);
states[next][2] = max(states[cur][2], states[cur][1]-prices[i]);
states[next][3] = max(states[cur][3], states[cur][2]+prices[i]);
swap(next, cur);
}
return max(states[cur][1], states[cur][3]);
}
};

https://discuss.leetcode.com/topic/27426/a-solution-not-so-dynamic-programming

A solution not so dynamic programming.

I think the most difficult part is how to connect the first transaction to the second transaction. The final target is to get the maximum value of profit2. You must try to get money as much as possible after you buy the stock second time. Then after the second time of sell, with the as high as possible price, you get the maximum profit.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
int maxProfit(vector<int>& prices) {
int size=prices.size();
int profit1=0;
int profit2=0;
int o1=INT_MAX;
int o2=INT_MIN;
for(int i=0; i<size; ++i){
o1=min(o1, prices[i]);
profit1=max(profit1, prices[i]-o1);
o2=max(o2, profit1-prices[i]);
profit2=max(profit2, prices[i]+o2);
}
return profit2;
}
};

https://discuss.leetcode.com/topic/902/don-t-need-dp-to-solve-it-within-o-n

Don’t need DP to solve it within O(n)

Don’t need DP to solve this problem. It is still O(n) and basically use the same algorithm solving “Stock I” four times.

  1. Get the max profit with one transaction to the full array. Keep down the start and end positions.

  2. the start and end positions will be included in the result of two transaction. It falls into two categories:
    A) it is one full transaction, B) they belong to two separate transactions(start belongs to first transaction and end belongs to second transaction).

  3. if A)– get max profit with one transaction to subarray from 0 to start ; get max profit with one transaction to subarray from end to prices.length.

  4. if B)– get the max profit with one transaction within start and end in reverse order

  5. return the max profit in those cases.


https://discuss.leetcode.com/topic/41049/clear-c-solution

Clear c++ solution

1
2
3
4
5
6
7
8
9
10
11
12
int maxProfit(vector<int>& prices) {
//It's wrong if you choose the minimum price for buy2 , but you can maximize the left money.
//
int buy1 = INT_MIN, sale1 = 0, buy2 = INT_MIN, sale2 = 0;
for(int i=0; i<prices.size(); i++){ //the more money left, the happier you will be
buy1 = max(buy1, -prices[i]); //left money after buy1
sale1 = max(sale1, prices[i] + buy1); //left money after sale1
buy2 = max(buy2, sale1 - prices[i]); //left money after buy2
sale2 = max(sale2, prices[i] + buy2); //left money after sale2
}
return sale2;
}

https://discuss.leetcode.com/topic/42087/why-don-t-we-make-our-life-easier

Why don’t we make our life easier

The idea is very basic. At most two transactions means we can break at any time point and compute the max revenue before this time point and after this time point. For every possible time point, we choose the maximum.

Note that right_max start from the last time point, which is just like a mirror algorithm from the Best Time to Buy and Sell Stock I

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
int maxProfit(vector<int>& prices) {
vector<int> left_max;
vector<int> right_max;
int n = prices.size();
if(n == 0){
return 0;
}
int cur_min = prices[0];
int max_r = 0;
for(int i = 0; i < n; i++){
max_r = max(max_r, prices[i] - cur_min);
left_max.push_back(max_r);
cur_min = min(cur_min, prices[i]);
}
int cur_max = prices[n-1];
max_r = 0;
for(int i = n-1; i >= 0; i--){
max_r = max(max_r, cur_max - prices[i]);
right_max.insert(right_max.begin(), max_r);
cur_max = max(cur_max, prices[i]);
}
int sum_max = 0;
for(int i = 0; i < n; i++){
sum_max = max(sum_max, left_max[i] + right_max[i]);
}
return sum_max;
}

python


https://discuss.leetcode.com/topic/6811/python-dp-solution-120ms

Python DP solution, 120ms

Two passes through the list, O(n) time, O(n) space:

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
def maxProfit(self, prices):
if not prices:
return 0

# forward traversal, profits record the max profit
# by the ith day, this is the first transaction
profits = []
max_profit = 0
current_min = prices[0]
for price in prices:
current_min = min(current_min, price)
max_profit = max(max_profit, price - current_min)
profits.append(max_profit)

# backward traversal, max_profit records the max profit
# after the ith day, this is the second transaction
total_max = 0
max_profit = 0
current_max = prices[-1]
for i in range(len(prices) - 1, -1, -1):
current_max = max(current_max, prices[i])
max_profit = max(max_profit, current_max - prices[i])
total_max = max(total_max, max_profit + profits[i])

return total_max

https://discuss.leetcode.com/topic/51468/7-liner-in-python-beats-99

7-liner in Python, beats 99%

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
def maxProfit(self, p):
if not p: return 0
sell, buyd, n, minp, maxp = [0], [0], len(p), p[0], p[-1]
for i in range(1, n):
minp, maxp = min(minp, p[i]), max(maxp, p[n-i-1])
sell.append(max(sell[i-1], p[i] - minp))
buyd.append(max(buyd[i-1], maxp - p[n-i-1]))
return max(sell[i] + buyd[n-i-1] for i in range(n))


# 198 / 198 test cases passed.
# Status: Accepted
# Runtime: 56 ms

java


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

Is it Best Solution with O(n), O(1).

The thinking is simple and is inspired by the best solution from Single Number II (I read through the discussion after I use DP).

Assume we only have 0 money at first;

4 Variables to maintain some interested ‘ceilings’ so far:

The maximum of if we’ve just buy 1st stock, if we’ve just sold 1nd stock, if we’ve just buy 2nd stock, if we’ve just sold 2nd stock.

Very simple code too and work well. I have to say the logic is simple than those in Single Number II.

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
public int maxProfit(int[] prices) {
int hold1 = Integer.MIN_VALUE, hold2 = Integer.MIN_VALUE;
int release1 = 0, release2 = 0;
for(int i:prices){ // Assume we only have 0 money at first
release2 = Math.max(release2, hold2+i); // The maximum if we've just sold 2nd stock so far.
hold2 = Math.max(hold2, release1-i); // The maximum if we've just buy 2nd stock so far.
release1 = Math.max(release1, hold1+i); // The maximum if we've just sold 1nd stock so far.
hold1 = Math.max(hold1, -i); // The maximum if we've just buy 1st stock so far.
}
return release2; ///Since release1 is initiated as 0, so release2 will always higher than release1.
}
}

https://discuss.leetcode.com/topic/4766/a-clean-dp-solution-which-generalizes-to-k-transactions

A clean DP solution which generalizes to k transactions

Solution is commented in the code. Time complexity is O(kn), space complexity can be O(n) because this DP only uses the result from last step. But for cleaness this solution still used O(kn) space complexity to preserve similarity to the equations in the comments.

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
class Solution {
public:
int maxProfit(vector<int> &prices) {
// f[k, ii] represents the max profit up until prices[ii] (Note: NOT ending with prices[ii]) using at most k transactions.
// f[k, ii] = max(f[k, ii-1], prices[ii] - prices[jj] + f[k-1, jj]) { jj in range of [0, ii-1] }
// = max(f[k, ii-1], prices[ii] + max(f[k-1, jj] - prices[jj]))
// f[0, ii] = 0; 0 times transation makes 0 profit
// f[k, 0] = 0; if there is only one price data point you can't make any money no matter how many times you can trade
if (prices.size() <= 1) return 0;
else {
int K = 2; // number of max transation allowed
int maxProf = 0;
vector<vector<int>> f(K+1, vector<int>(prices.size(), 0));
for (int kk = 1; kk <= K; kk++) {
int tmpMax = f[kk-1][0] - prices[0];
for (int ii = 1; ii < prices.size(); ii++) {
f[kk][ii] = max(f[kk][ii-1], prices[ii] + tmpMax);
tmpMax = max(tmpMax, f[kk-1][ii] - prices[ii]);
maxProf = max(f[kk][ii], maxProf);
}
}
return maxProf;
}
}
};

https://discuss.leetcode.com/topic/4766/a-clean-dp-solution-which-generalizes-to-k-transactions/2

Brilliant solution! a small point: there is no need to track maxProf. we can simply return f[K][prices.size()-1]

https://discuss.leetcode.com/topic/4766/a-clean-dp-solution-which-generalizes-to-k-transactions/9

Brilliant solution! Thanks for sharing~

Minor point, but f[kk-1][0] is just 0.

I’d also explain the algorithm a little differently, something like the following:

1
2
3
4
5
6
// dpProfit[t][i]: maximum Profit using at most t transactions up to day i (including day i)
// dpProfit[t][i] = max(dpProfit[t][i - 1], prices[i] - prices[j] + dpProfit[t - 1][j]) for all j in range [0, i - 1]
// = max(dpProfit[t][i - 1], prices[i] + max(dpProfit[t - 1][j] - prices[j])) for all j in range [0, i - 1]
// = max(dpProfit[t][i - 1], prices[i] + max prev [t - 1] trans profit at the corresponding j in range [0, i - 1] less price at j)
// maxPreProfitLessI inside loop iterations
// Note: subtracting price at j is for the last additional transaction to sell at day i

https://discuss.leetcode.com/topic/39751/my-explanation-for-o-n-solution

My explanation for O(N) solution!

First assume that we have no money, so buy1 means that we have to borrow money from others, we want to borrow less so that we have to make our balance as max as we can(because this is negative).

sell1 means we decide to sell the stock, after selling it we have price[i] money and we have to give back the money we owed, so we have price[i] - |buy1| = prices[i ] + buy1, we want to make this max.

buy2 means we want to buy another stock, we already have sell1 money, so after buying stock2 we have buy2 = sell1 - price[i] money left, we want more money left, so we make it max

sell2 means we want to sell stock2, we can have price[i] money after selling it, and we have buy2 money left before, so sell2 = buy2 + prices[i], we make this max.

So sell2 is the most money we can have.

Hope it is helpful and welcome quesions!

1
2
3
4
5
6
7
8
9
10
public int maxProfit(int[] prices) {
int sell1 = 0, sell2 = 0, buy1 = Integer.MIN_VALUE, buy2 = Integer.MIN_VALUE;
for (int i = 0; i < prices.length; i++) {
buy1 = Math.max(buy1, -prices[i]);
sell1 = Math.max(sell1, buy1 + prices[i]);
buy2 = Math.max(buy2, sell1 - prices[i]);
sell2 = Math.max(sell2, buy2 + prices[i]);
}
return sell2;
}

https://discuss.leetcode.com/topic/32288/2ms-java-dp-solution

2ms Java DP Solution

Sorry for my poor English

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int maxProfit(int[] prices) {
// these four variables represent your profit after executing corresponding transaction
// in the beginning, your profit is 0.
// when you buy a stock ,the profit will be deducted of the price of stock.
int firstBuy = Integer.MIN_VALUE, firstSell = 0;
int secondBuy = Integer.MIN_VALUE, secondSell = 0;

for (int curPrice : prices) {
if (firstBuy < -curPrice) firstBuy = -curPrice; // the max profit after you buy first stock
if (firstSell < firstBuy + curPrice) firstSell = firstBuy + curPrice; // the max profit after you sell it
if (secondBuy < firstSell - curPrice) secondBuy = firstSell - curPrice; // the max profit after you buy the second stock
if (secondSell < secondBuy + curPrice) secondSell = secondBuy + curPrice; // the max profit after you sell the second stock
}

return secondSell; // secondSell will be the max profit after passing the prices
}

https://discuss.leetcode.com/topic/7028/java-solution-with-just-two-traverses

Java solution with just two traverses.

Go from left to right and calculate max profit for each index (i). Go from right to left and calculate max profit for (i). Add max right profit for (i) and max left profit for (i-1) and check if it’s max profit.

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
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) return 0;
int lenght = prices.length;

int[] leftProfit = new int[lenght];
int leftMaxProfit = 0;
int leftMin = prices[0];
for (int i=0; i<lenght; i++) {
if (prices[i] < leftMin) leftMin = prices[i];
if (prices[i] - leftMin > leftMaxProfit) leftMaxProfit = prices[i]-leftMin;
leftProfit[i] = leftMaxProfit;
}

int maxProfit = 0;
int rightMaxProfit = 0;
int rightMax = prices[lenght-1];
for (int i=lenght-1; i>=0; i--) {
if (prices[i] > rightMax) rightMax = prices[i];
if (rightMax - prices[i] > rightMaxProfit) rightMaxProfit = rightMax - prices[i];
int currentProfit = rightMaxProfit + (i>0 ? leftProfit[i-1] : 0);
if (currentProfit > maxProfit) {
maxProfit = currentProfit;
}
}

return maxProfit;
}

my code

dp1中的dp[i] 表示从第一天至第i天,只卖出一次的最大收益。

dp2中的dp[i] 表示从第i天至最后一天,只卖出一次的最大收益。

dp1从前向后,dp2从后向前

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 {
public int maxProfit(int[] prices) {
int[] dp1 = new int[prices.length];
int[] dp2 = new int[prices.length];
int minprice = Integer.MAX_VALUE;
int maxprofit = 0;
for(int i=0; i<prices.length; i++){
if(prices[i] < minprice)
minprice = prices[i];
else
maxprofit = Math.max(maxprofit, prices[i]-minprice);
dp1[i] = maxprofit;
}
int maxprice = Integer.MIN_VALUE;
maxprofit = 0;
for(int j=prices.length-1; j>=0; j--){
if(prices[j] > maxprice)
maxprice = prices[j];
else
maxprofit = Math.max(maxprofit, maxprice-prices[j]);
dp2[j] = maxprofit;
}
maxprofit = 0;
for(int i=0; i<prices.length; i++)
maxprofit = Math.max(maxprofit, dp1[i]+dp2[i]);
return maxprofit;
}
}
谢谢你,可爱的朋友。