- 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 | class Solution { |

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 | class Solution { |

方法二：

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

1 | class Solution { |

#### 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 | class Solution { |

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 | class Solution { |

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.

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

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).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.

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

return the max profit in those cases.

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

Clear c++ solution

1 | int maxProfit(vector<int>& prices) { |

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 | int maxProfit(vector<int>& prices) { |

#### 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 | def maxProfit(self, prices): |

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

7-liner in Python, beats 99%

1 | class Solution(object): |

#### 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 | public class Solution { |

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 | class Solution { |

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 | // dpProfit[t][i]: maximum Profit using at most t transactions up to day i (including 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 | public int maxProfit(int[] prices) { |

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

2ms Java DP Solution

Sorry for my poor English

1 | public int maxProfit(int[] 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 | public int maxProfit(int[] prices) { |

my code

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

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

dp1从前向后，dp2从后向前

1 | public class Solution { |