Given a list containing future prediction of share prices, find maximum profit that can be earned by buying and selling shares at most k times 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 Price: {2, 4, 7, 5, 4, 3, 5}

K = 2

**Output:** Maximum profit is 7 (sum of 5 and 2)

Buy at price 2 and sell at price 7

Buy at price 3 and sell at price 5

**Input:**

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

K = 3

**Output:** Maximum profit is 10 (sum of 4, 5 and 1)

Buy at price 1 and sell at price 5

Buy at price 2 and sell at price 7

Buy at price 4 and sell at price 5

**Input:**

Stock Price: {10, 6, 8, 4, 2}

K = 2

**Output:** Maximum profit is 2

Buy at price 6 and sell at price 8

**Input:**

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

K = 1

**Output:** Maximum profit 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 any number of times, we can follow the approach discussed here.

Now we’re only allowed to make at most k stock transactions. The problem can be solve by using Dynamic Programming. Let `T[t][i]` be the maximum profit using at most t transactions till the `i'th` day. Then, `T[i]` can be written as –

`T[t][i] = max(T[t][i-1], max(price[i] – price[j] + T[t-1][j]) |
where j varies from 0 to i-1)`

Above relation states that `T[t][i]` would be maximum of –

`T[t][i-1]`which represents not doing any transaction on the`i'th`day.

- Maximum profit gained by selling on the
`i'th`day. In order to sell shares on the`i'th`day, we need to purchase it on any one of previous days. If we buy shares on the`j'th`day and sell it on the`i'th`day, the maximum profit will be`price[i] – price[j] + T[t-1][j]`

where`j`varies from`0`to`i-1`and`T[t-1][j]`is the best with one less transaction till the`j'th`day.

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 |
#include <iostream> #include <vector> using namespace std; // Find maximum profit earned from at most k stock transactions // Input to the function are stock prices of n days and positive number k int maxProfit(vector<int> &price, int k) { // get number of days n int n = price.size(); // profit[i][j] stores the maximum profit gained by doing // at most i transactions till j'th day int profit[k+1][n]; // fill profit[][] matrix in bottom-up fashion for (int i = 0; i <= k; i++) { for (int j = 0; j < n; j++) { // profit is 0 when: // i = 0 i.e. for 0'th day // j = 0 i.e. no transaction is being performed if (i == 0 || j == 0) { profit[i][j] = 0; } else { int max_so_far = 0; for (int k = 0; k < j; k++) { int curr_price = price[j] - price[k] + profit[i-1][k]; if (max_so_far < curr_price) { max_so_far = curr_price; } } profit[i][j] = max(profit[i][j-1], max_so_far); } } } return profit[k][n-1]; } int main() { vector<int> price { 1, 5, 2, 3, 7, 6, 4, 5 }; int k = 3; cout << "The maximum possible profit is: " << maxProfit(price, k); return 0; } |

`Output:`

The maximum possible profit is: 10

The time complexity of above solution is `O(n ^{2}k)` and auxiliary space required by the program is

`O(nk)`. The code can be easily optimized to run in

`O(nk)`time if we’re able to calculate the maximum profit gained by selling shares on the

`i'th`day in constant time.

### Optimized Solution:

We have already seen that `T[i]` can be written as –

`T[t][i] = max(T[t][i-1], max(price[i] – price[j] + T[t-1][j]) |
where j varies from 0 to i-1)`

If we carefully notice, `max(price[i] – price[j] + T[t-1][j])`

can be rewritten as,

` = price[i] + max(T[t-1][j] – price[j]) where j varies from 0 to i-1`

` = price[i] + max(prev_diff, T[t-1][i-1] – price[i-1])
where prev_diff is max(T[t-1][j] – price[j])
where j varies from 0 to i-2`

Since we have already calculated `max(T[t-1][j] – price[j])`

for every `j` within the range `[0,i-2]`, we can easily calculate it for `j=i–1` in `O(1)` time. In other words, we don’t have revisit the range `[0,i-1]` to figure out the best day for buying stock. This can be determined in `O(1)` time using below revised relation –

`T[t][i] = max(T[t][i-1], price[i] + max(prev_diff, T[t-1][i-1] – price[i-1]) |
where prev_diff is max(T[t-1][j] – price[j])
where j varies from 0 to i-2`

This is demonstrated below 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 |
#include <iostream> #include <vector> #include <climits> #include <algorithm> using namespace std; // Find maximum profit earned from at most k stock transactions // Input to the function are stock prices of n days and positive number k int maxProfit(vector<int>& price, int k) { // get number of days n int n = price.size(); // profit[i][j] stores the maximum profit gained by doing // at most i transactions till j'th day int profit[k+1][n+1]; // fill profit[][] matrix in bottom-up fashion for (int i = 0; i <= k; i++) { // initialize prev diff to minus infinity int prev_diff = INT_MIN; for (int j = 0; j < n; j++) { // profit is 0 when: // i = 0 i.e. for 0'th day // j = 0 i.e. no transaction is being performed if (i == 0 || j == 0) { profit[i][j] = 0; } else { prev_diff = max(prev_diff, profit[i - 1][j - 1] - price[j - 1]); profit[i][j] = max(profit[i][j - 1], price[j] + prev_diff); } } } return profit[k][n - 1]; } int main() { vector<int> price { 1, 5, 2, 3, 7, 6, 4, 5 }; int k = 3; cout << "The maximum possible profit is: " << maxProfit(price, k); return 0; } |

`Output:`

The maximum possible profit is: 10

The time complexity of above solution is `O(nk)` and auxiliary space required by the program is `O(nk)`. The space complexity can further be reduced to `O(n)` since we only need results from the last transaction.

**Author:** Aditya Goel

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