Find maximum profit earned from at most two stock transactions

Given a list containing future prediction of share prices, find maximum profit that can be earned by buying and selling shares at most twice with a constraint that a new transaction can only start after previous transaction is complete. i.e. we can only hold at most one share at a time.


 

For example,


Input: Stock Prices are {2, 4, 7, 5, 4, 3, 5}
Output: The maximum profit is 7

Buy at price 2 and sell at price 7
Buy at price 3 and sell at price 5

 
Input: Stock Prices are {10, 6, 8, 4, 2}
Output: The maximum profit is 2

Buy at price 6 and sell at price 8

 
Input: Stock Prices are {8, 7, 6, 4}
Output: The maximum profit is 0

Buying and selling stock will result in loss

 

 
There are several variations to above problem –

  1. If we’re allowed to stock only once, then we can find maximum difference between two elements in the array where the smaller element appears before the larger element.
     
  2. If we’re allowed to stock shares at most k times, we can follow the approach discussed here.
     
  3. If we’re allowed to stock shares any number of times, we can follow the approach discussed here.
     

 
Here we’re allowed to stock shares at most 2 times. The idea is to use extra space to solve this problem. We create an auxiliary array (say profit[]) and fill it while performing two scans of the input array which contains the stock price information for each day.

  1. In the first scan, we update profit[i] to the maximum profit earned by a single stock transaction from day i to day n-1. This can be done by traversing the array from right to left and keeping track of maximum stock price seen so far.
     
  2. In the second scan, we update profit[i] by taking the maximum of profit[i-1] (i.e. maximum profit calculated so far) and the total profit obtained by closing the first transaction on day i and performing another transaction from day i to day n-1. We can find the maximum profit earned on a stock transaction closing on day i by traversing the array from left to right and keeping track of minimum stock price seen so far.

 
Finally, the last element of profit[] has the result.

 
Note we can initiate the second transaction on the same day of closing the first transaction. i.e. at the same price. This does not voilate the problem constraint that a second transaction can only start once the first transaction is complete. This essentially means that we have performed only a single transaction.

The algorithm can be implemented as follows in C:

 

Download   Run Code

Output:

The maximum profit is 7

 
The time complexity of above solution is O(n) and auxiliary space required by the program is O(n).

 
1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Leave a Reply

avatar
  Subscribe  
Notify of