## Best time to buy and sell stock III

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

*two*transactions.**Note:**

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

### Analysis:

The idea is from dynamic programming, the max profit at day i is the max profit before day i + max profit after day i. So there is one loop O(n) to compute the max profit before each each day and another loop O(n) to get the final max profit by compute the max profit after each day reversely and combine the "before day" max profit.

Let's take an example:

prices[ ] = 1,2,4,2,5,7,2,4,9

(1) we compute the forward max profit and save it. Forward max profit means for each day i, we want to know the max profit we can make no later than this day. Note that we only need to consider 1 transaction:

prices[ ] = 1,2,4,2,5,7,2,4,9

mp[ ] = 0,1,3,3,4,6,6,6,8

(2) Now what we need is two transactions rather than one, easily we can see from the price list, if we are required exact 2 transactions, we must finish one transaction at some day i, and do the 2nd transaction after that.

Similar to the step(1), but in a reverse order, from the last day -1 to first, we already have the max profit before day i, mp[i], and we can compute the max profit every time for i to n-1 days (n is the number of days), similar to step(1).

e.g.

max_profit = mp[i] + mprofit

i

prices[ ] = 1,2,4,2,5,7,2,4,9

mp[ ] = 0,1,3,3,4,6,6,6,8

max_profit = 6 + (9-4) = 11 (2nd trans. : buy at $4 sell at $9)

i

prices[ ] = 1,2,4,2,5,7,2,4,9

mp[ ] = 0,1,3,3,4,6,6,6,8

max_profit = 6+ (9-2) = 13 (2nd trans. : buy at $2 sell at $9)

i

prices[ ] = 1,2,4,2,5,7,2,4,9

mp[ ] = 0,1,3,3,4,6,6,6,8

max_profit = 6+ (9-2) = 13 (max profit after day i not change)

i

prices[ ] = 1,2,4,2,5,7,2,4,9

mp[ ] = 0,1,3,3,4,6,6,6,8

max_profit = 13

The final max profit =13

(If you see the case that sell and buy on the same day, this is equal to the case that only 1 transaction. So the "at most 2 transactions" is satisfied)

Let's take an example:

prices[ ] = 1,2,4,2,5,7,2,4,9

(1) we compute the forward max profit and save it. Forward max profit means for each day i, we want to know the max profit we can make no later than this day. Note that we only need to consider 1 transaction:

prices[ ] = 1,2,4,2,5,7,2,4,9

mp[ ] = 0,1,3,3,4,6,6,6,8

(2) Now what we need is two transactions rather than one, easily we can see from the price list, if we are required exact 2 transactions, we must finish one transaction at some day i, and do the 2nd transaction after that.

**The max profit is the sum of max profit before day i and after day i**. Day i might be every day in the price list, so there is a loop in the code.Similar to the step(1), but in a reverse order, from the last day -1 to first, we already have the max profit before day i, mp[i], and we can compute the max profit every time for i to n-1 days (n is the number of days), similar to step(1).

e.g.

max_profit = mp[i] + mprofit

i

prices[ ] = 1,2,4,2,5,7,2,4,9

mp[ ] = 0,1,3,3,4,6,6,6,8

max_profit = 6 + (9-4) = 11 (2nd trans. : buy at $4 sell at $9)

i

prices[ ] = 1,2,4,2,5,7,2,4,9

mp[ ] = 0,1,3,3,4,6,6,6,8

max_profit = 6+ (9-2) = 13 (2nd trans. : buy at $2 sell at $9)

i

prices[ ] = 1,2,4,2,5,7,2,4,9

mp[ ] = 0,1,3,3,4,6,6,6,8

max_profit = 6+ (9-2) = 13 (max profit after day i not change)

**......**i

prices[ ] = 1,2,4,2,5,7,2,4,9

mp[ ] = 0,1,3,3,4,6,6,6,8

max_profit = 13

The final max profit =13

(If you see the case that sell and buy on the same day, this is equal to the case that only 1 transaction. So the "at most 2 transactions" is satisfied)

### Source Code: O(n)

class Solution { public: int maxProfit(vector<int> &prices) { // Start typing your C/C++ solution below // DO NOT write int main() function int mprof = 0; if (prices.size()>1){ int maxprof = 0; vector<int> mp; // max profit before each element mp.push_back(0); int st = *prices.begin(); for(int i = 1 ; i<=prices.size();i++){ //compute mp vector if (mprof < prices[i]-st){mprof = prices[i]-st;} if (prices[i]<st){st = prices[i];} mp.push_back(mprof); } mprof = 0; int ed = *(prices.end()-1); for (int i = prices.size()-2; i>=0; i--){ if (mprof < ed - prices[i] + mp[i]) { mprof = ed - prices[i] + mp[i];} if (prices[i]>ed) {ed = prices[i];} } } return mprof; } };

### Code (Python):

class Solution: # @param prices, a list of integer # @return an integer def maxProfit(self, prices): n = len(prices) if (n<2): return 0 st = prices[0] mp=[] mprof = 0 for i in range(0,n): if (prices[i]-st>mprof): mprof = prices[i]-st if (prices[i]<st): st = prices[i] mp.append(mprof) mprof = 0 ed = prices[-1] for i in range(n-2,-1,-1): if (ed - prices[i] + mp[i] > mprof): mprof = ed - prices[i] + mp[i] if (prices[i]>ed): ed = prices[i] return mprof

It is a very nice solution, simple and clear.

ReplyDeleteHope I could be as swift as you are when I am on my interview for these questions.

Are you an algorithm professor in Univ. of WV?

Thanks!

DeleteI'm a phd student in WVU. lol

But you cannot buy and sell at the same day right? mprof = ed - prices[i] + mp[i-1] ?

ReplyDeletePlease also give the solution for the problem "Best time to buy and sell stock IV"

ReplyDeleteThanks..

By far one of the best solution i've seen. Simple, clear, effective

ReplyDelete