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.

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

- 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 k times, we can follow the approach discussed here.

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

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

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

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 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
#include <stdio.h> inline int max(int x, int y) { return (x > y) ? x: y; } inline int min(int x, int y) { return (x < y) ? x: y; } // Function to find maximum profit earned from at most two stock transactions int findMaxProfit(int price[], int n) { // create an auxiliary array of size n int profit[n]; // initialize last element of the auxiliary array to 0 profit[n-1] = 0; // to keep track of maximum stock price on the right of current stock price int max_so_far = price[n - 1]; // traverse the array from right to left for (int i = n - 2; i >= 0; i--) { // update profit[i] to the maximum profit earned by a single stock // transaction from day i to day n-1 profit[i] = max(profit[i + 1], max_so_far - price[i]); // update maximum stock price seen so far max_so_far = max(max_so_far, price[i]); } // to keep track of minimum stock price to the left of current stock price int min_so_far = price[0]; // traverse the array from left to right for (int i = 1; i < n; i++) { // update profit[i] by taking the maximum of: // 1. profit[i-1] which represents the maximum profit calculated so far // 2. total profit of obtained by closing the first transaction on day i // and performing another transaction from day i to day n-1. profit[i] = max(profit[i - 1], (price[i] - min_so_far) + profit[i]); // update minimum stock price seen so far min_so_far = min(min_so_far, price[i]); } // the last element of profit[] stores the result return profit[n - 1]; } int main() { int price[] = { 2, 4, 7, 5, 4, 3, 5 }; int n = sizeof(price) / sizeof(price[0]); printf("The maximum profit is %d", findMaxProfit(price, n)); return 0; } |

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

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