Maximum profit earned by buying and selling shares any number of times

Given a list containing future prediction of share prices, find maximum profit that can be earned by buying and selling shares any number of times with 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,


Stock Prices:  {1, 5, 2, 3, 7, 6, 4, 5}

Total profit earned is 10

Buy on day 1 and sell on day 2
Buy on day 3 and sell on day 5
Buy on day 7 and sell on day 8

 
Stock Prices: {10, 8, 6, 5, 4, 2}

Total profit earned is 0

 
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 twice, we can follow the approach discussed here.
     
  3. If we’re allowed to stock shares at most k times, we can follow the approach discussed here.
     

 
Here, we’re allowed to make unlimited stock transactions. The idea is to traverse the given list of prices and find local minimum of every increasing sequence.

For example, in the array {1, 5, 2, 3, 7, 6, 4, 5}, below are three increasing sequences of length 2 or more.

{1, 5}
{2, 3, 7}
{4, 5}

The local minimum of each sequence is 1, 2 and 4 respectively. We can gain maximum profit if we buy the shares at the starting of every increasing sequence (local minimum) and sell them at the end of the increasing sequence (local maximum).

C

Download   Run Code

Java

Download   Run Code

Output:

Buy on day 1 and sell on day 2
Buy on day 3 and sell on day 5
Buy on day 7 and sell on day 8

Total profit earned is 10

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

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 






Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
Vikky Agrawal
Guest
Vikky Agrawal

Nice thinking

gawkface
Guest
gawkface

simpler logic using c++ min, max algorithms

Jinchul
Guest
Jinchul

My solution using C++: http://rextester.com/UFRK8796