Find maximum profit earned from at most `k` stock transactions
Given a list containing future predictions of share prices, find the maximum profit earned by buying and selling shares at most k times with a constraint that a new transaction can only start after the 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: The maximum profit is 7 (sum of 5 and 2)
Buy at a price 2 and sell at a price 7
Buy at a price 3 and sell at a price 5
Input:
Stock Price: {1, 5, 2, 3, 7, 6, 4, 5}
k = 3
Output: The maximum profit is 10 (sum of 4, 5 and 1)
Buy at a price 1 and sell at a price 5
Buy at a price 2 and sell at a price 7
Buy at a price 4 and sell at a price 5
Input:
Stock Price: {10, 6, 8, 4, 2}
k = 2
Output: The maximum profit is 2
Buy at a price 6 and sell at a price 8
Input:
Stock Price: {10, 8, 6, 5, 4, 2}
k = 1
Output: The maximum profit is 0
There are several variations to the above problem:
- If we are allowed to stock only once, then we can find the maximum difference between two elements in the array, where the smaller element appears before the larger element.
- If we are allowed to stock shares at most twice, we can follow the approach discussed here.
- If we are allowed to stock shares any number of times, we can follow the approach discussed here.
Now we are only allowed to make at most k stock transactions. We can solve the problem by using dynamic programming. Let T[t][i] be the maximum profit using most t transactions till the i'th day. Then T[i] can be written as:
where j varies from 0 to i-1
The above relation states that T[t][i] would be a maximum of below:
T[t][i-1], which represents not doing any transaction on thei'thday.- Maximum profit gained by selling on the
i'thday. To sell shares on thei'thday, we need to purchase them on any previous day. If we buy shares on thej'thday and sell it on thei'thday, the maximum profit will beprice[i] - price[j] + T[t-1][j], wherejvaries from 0 toi-1andT[t-1][j]is the best with one less transaction till thej'thday.
The algorithm can be implemented as follows in C++, Java, and Python:
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 59 |
#include <iostream> #include <vector> using namespace std; // Find maximum profit earned from at most `k` stock transactions. // Input to the function is stock prices of `n` days and positive number `k` int findMaxProfit(vector<int> const &price, int k) { // get the number of days `n` int n = price.size(); // base case if (n <= 1) { return 0; } // 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[][] in a 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 0th 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 " << findMaxProfit(price, k); return 0; } |
Output:
The maximum possible profit is 10
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 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
class Main { // Find maximum profit earned from at most `k` stock transactions. // Input to the function is stock prices of `n` days and positive number `k` public static int findMaxProfit(int[] price, int k) { // get the number of days `n` int n = price.length; // base case if (n <= 1) { return 0; } // profit[i][j] stores the maximum profit gained by doing // at most `i` transactions till j'th day int[][] profit = new int[k + 1][n]; // fill profit[][] in a 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 0th 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 x = 0; x < j; x++) { int curr_price = price[j] - price[x] + profit[i-1][x]; if (max_so_far < curr_price) { max_so_far = curr_price; } } profit[i][j] = Math.max(profit[i][j-1], max_so_far); } } } return profit[k][n-1]; } public static void main(String[] args) { int[] price = { 1, 5, 2, 3, 7, 6, 4, 5 }; int k = 3; System.out.println("The maximum possible profit is " + findMaxProfit(price, k)); } } |
Output:
The maximum possible profit is 10
Python
|
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 |
# Find maximum profit earned from at most `k` stock transactions. # Input to the function is stock prices of `n` days and positive number `k` def findMaxProfit(price, k): # get the number of days `n` n = len(price) # base case if n <= 1: return 0 # profit[i][j] stores the maximum profit gained by doing # at most `i` transactions till j'th day profit = [[0 for x in range(n)] for y in range(k + 1)] # fill profit[][] in a bottom-up fashion for i in range(k + 1): for j in range(n): # profit is 0 when # i = 0, i.e., for 0th day # j = 0, i.e., no transaction is being performed if i == 0 or j == 0: profit[i][j] = 0 else: max_so_far = 0 for x in range(j): curr_price = price[j] - price[x] + profit[i-1][x] 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] if __name__ == '__main__': price = [1, 5, 2, 3, 7, 6, 4, 5] k = 3 print('The maximum possible profit is', findMaxProfit(price, k)) |
Output:
The maximum possible profit is 10
The time complexity of the above solution is O(n2k) and requires O(n.k) extra space, where n is the total number of given days and k is the maximum number of allowed stock transactions. We can easily optimize the code to run in O(n.k) time if we can 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:
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(prev_diff, T[t-1][i-1] – price[i-1])
where prev_diff is max(T[t-1][j] – price[j]) and j varies from 0 to i-2
Since we have already calculated max(T[t-1][j] - price[j]) for every j within range [0, i-2], we can easily calculate it for j=i-1 in O(1) time. In other words, we don’t have to revisit range [0, i-1] to figure out the best day for buying stock. This can be determined in O(1) time using the following revised relation:
where prev_diff is max(T[t-1][j] – price[j]) and j varies from 0 to i-2
The algorithm can be implemented as follows in C++, Java, and Python:
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 |
#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 is stock prices of `n` days and positive number `k` int findMaxProfit(vector<int> const &price, int k) { // get the number of days `n` int n = price.size(); // base case if (n <= 1) { return 0; } // 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[][] in a bottom-up fashion for (int i = 0; i <= k; i++) { // initialize `prev` diff to `-INFINITY` int prev_diff = INT_MIN; for (int j = 0; j < n; j++) { // profit is 0 when: // i = 0, i.e., for 0th 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 " << findMaxProfit(price, k); return 0; } |
Output:
The maximum possible profit is 10
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 43 44 45 46 47 48 49 50 |
class Main { // Find maximum profit earned from at most `k` stock transactions. // Input to the function is stock prices of `n` days and positive number `k` public static int findMaxProfit(int[] price, int k) { // get the number of days `n` int n = price.length; // base case if (n <= 1) { return 0; } // profit[i][j] stores the maximum profit gained by doing // at most `i` transactions till j'th day int[][] profit = new int[k+1][n+1]; // fill profit[][] in a bottom-up fashion for (int i = 0; i <= k; i++) { // initialize `prev` diff to int prev_diff = Integer.MIN_VALUE; for (int j = 0; j < n; j++) { // profit is 0 when: // i = 0, i.e., for 0th day // j = 0, i.e., no transaction is being performed if (i == 0 || j == 0) { profit[i][j] = 0; } else { prev_diff = Math.max(prev_diff, profit[i-1][j-1] - price[j-1]); profit[i][j] = Math.max(profit[i][j-1], price[j] + prev_diff); } } } return profit[k][n - 1]; } public static void main(String[] args) { int[] price = {1, 5, 2, 3, 7, 6, 4, 5}; int k = 3; System.out.println("The maximum possible profit is " + findMaxProfit(price, k)); } } |
Output:
The maximum possible profit is 10
Python
|
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 |
import sys # Find maximum profit earned from at most `k` stock transactions. # Input to the function is stock prices of `n` days and positive number `k` def findMaxProfit(price, k): # get the number of days `n` n = len(price) # base case if n <= 1: return 0 # profit[i][j] stores the maximum profit gained by doing # at most `i` transactions till j'th day profit = [[0 for x in range(n + 1)] for y in range(k + 1)] # fill profit[][] in a bottom-up fashion for i in range(k + 1): # initialize `prev` diff to `-INFINITY` prev_diff = -sys.maxsize for j in range(n): # profit is 0 when # i = 0, i.e., for 0th day # j = 0, i.e., no transaction is being performed if i == 0 or 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] if __name__ == '__main__': price = [1, 5, 2, 3, 7, 6, 4, 5] k = 3 print('The maximum possible profit is', findMaxProfit(price, k)) |
Output:
The maximum possible profit is 10
The time complexity of the above solution is O(n.k) and requires O(n.k) extra space, where n is the total number of given days and k is the maximum number of allowed stock transactions. The space complexity can be further reduced to O(n) since we only need results from the last transaction.
Author: Aditya Goel
Find maximum profit earned from at most two stock transactions
Find maximum profit earned by buying and selling shares any number of times
Find maximum profit that can be earned by conditionally selling stocks
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)