Find maximum profit earned from at most K 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 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.

For example,

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 –

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

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

2. 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++:

Output:

The maximum possible profit is: 10

The time complexity of above solution is O(n2k) 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++:

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.

(1 votes, average: 5.00 out of 5)