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.

**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 –

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

- If we’re allowed to stock shares at most twice, we can follow the approach discussed here.

- 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

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 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
#include <stdio.h> // Function to find maximum profit that can be earned by buying and // selling shares any number of times int maxProfit(int price[], int n) { // store maximum profit gained int profit = 0; // initialize local minimum to first element's index int j = 0; // start from second element for (int i = 1; i < n; i++) { // update local minimum if decreasing sequence is found if (price[i - 1] > price[i]) j = i; // sell shares if current element is peak // i.e. (previous < current > next) if (price[i - 1] < price[i] && (i + 1 == n || price[i] > price[i + 1])) { profit += (price[i] - price[j]); printf("Buy on day %d and sell on day %d\n", j + 1, i + 1); } } return profit; } // main function int main() { int price[] = { 1, 5, 2, 3, 7, 6, 4, 5 }; int n = sizeof(price) / sizeof(price[0]); printf("\nTotal profit earned is %d", maxProfit(price, n)); return 0; } |

## Java

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 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
class StockTransactions { // Function to find maximum profit that can be earned by buying and // selling shares any number of times public static int maxProfit(int[] price) { // store maximum profit gained int profit = 0; // initialize local minimum to first element's index int j = 0; // start from second element for (int i = 1; i < price.length; i++) { // update local minimum if decreasing sequence is found if (price[i - 1] > price[i]) { j = i; } // sell shares if current element is peak // i.e. (previous < current > next) if (price[i - 1] < price[i] && (i + 1 == price.length || price[i] > price[i + 1])) { profit += (price[i] - price[j]); System.out.printf("Buy on day %d and sell on day %d\n", j + 1, i + 1); } } return profit; } // main function public static void main(String[] args) { int[] price = { 1, 5, 2, 3, 7, 6, 4, 5 }; System.out.print("\nTotal profit earned is " + maxProfit(price)); } } |

`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

Nice thinking

simpler logic using c++ min, max algorithms

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