Find maximum profit that can be earned by conditionally selling stocks
Given a list containing future price predictions of two different stocks for the next n–days, find the maximum profit earned by selling the stocks with a constraint that the second stock can be sold, only if no transaction happened on the previous day for any of the stock.
Assume that the given prices are relative to the buying price. Each day, we can either sell a single share of the first stock or a single share of the second stock or sell nothing.
For example,
Day Price(x) Price(y)
1 5 8
2 3 4
3 4 3
4 6 5
5 3 10
Output: Maximum profit earned is 25
Explanation:
Day 1: Sell stock y at a price of 8
Day 2: Sell stock x at a price of 3
Day 3: Sell stock x at a price of 4
Day 4: Don’t sell anything
Day 5: Sell stock y at a price of 10
The idea is to use recursion to solve this problem in a top-down manner. To find the maximum profit till n'th day, there are two possible options:
- Sell the first stock on the
n'thday, and then recursively calculate the maximum profit till the(n-1)'thday. - Sell the second stock on the
n'thday, skip the(n-1)'thday, and then recursively calculate the maximum profit till the(n-2)'thday.
Accordingly, consider the maximum profit possible by either selling the first stock or the second stock on the n'th day. 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 |
#include <iostream> #include <vector> #include <algorithm> using namespace std; // Recursive function to find the maximum profit that can be earned by selling stocks. // Here, arrays `x[0…n]` and `y[0…n]` contains the two different stocks' future // price predictions for the next n–days. int findMaxProfit(vector<int> const &x, vector<int> const &y, int n) { // base case if (n < 0) { return 0; } // store the maximum profit gained int profit = 0; // sell the first stock on the n'th day, and recur for the (n-1)'th day profit = max(profit, x[n] + findMaxProfit(x, y, n - 1)); // sell the second stock on the n'th day, and recur for the (n-2)'th day // (no transaction can be made on the (n-1)'th day) profit = max(profit, y[n] + findMaxProfit(x, y, n - 2)); // return the maximum profit return profit; } int main() { vector<int> x = { 5, 3, 4, 6, 3 }; vector<int> y = { 8, 4, 3, 5, 10 }; int n = x.size(); cout << "The maximum profit earned is " << findMaxProfit(x, y, n - 1); return 0; } |
Output:
The maximum profit earned is 25
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 |
class Main { // Recursive function to find the maximum profit that can be earned by selling // stocks. Here, arrays `x[0…n]` and `y[0…n]` contains the two different stocks' // future price predictions for the next n–days. public static int findMaxProfit(int[] x, int[] y, int n) { // base case if (n < 0) { return 0; } // store the maximum profit gained int profit = 0; // sell the first stock on the n'th day, and recur for the (n-1)'th day profit = Integer.max(profit, x[n] + findMaxProfit(x, y, n - 1)); // sell the second stock on the n'th day, and recur for the (n-2)'th day // (no transaction can be made on the (n-1)'th day) profit = Integer.max(profit, y[n] + findMaxProfit(x, y, n - 2)); // return the maximum profit return profit; } public static void main(String[] args) { int[] x = { 5, 3, 4, 6, 3 }; int[] y = { 8, 4, 3, 5, 10 }; System.out.println("The maximum profit earned is " + findMaxProfit(x, y, x.length - 1)); } } |
Output:
The maximum profit earned is 25
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 |
# Recursive function to find the maximum profit that can be earned by selling stocks. # Here, arrays `x[0…n]` and `y[0…n]` contains the two different stocks' # future price predictions for the next n–days. def findMaxProfit(x, y, n): # base case if n < 0: return 0 # store the maximum profit gained profit = 0 # sell the first stock on the n'th day, and recur for the (n-1)'th day profit = max(profit, x[n] + findMaxProfit(x, y, n - 1)) # sell the second stock on the n'th day, and recur for the (n-2)'th day # (no transaction can be made on the (n-1)'th day) profit = max(profit, y[n] + findMaxProfit(x, y, n - 2)) # return the maximum profit return profit if __name__ == '__main__': x = [5, 3, 4, 6, 3] y = [8, 4, 3, 5, 10] print('The maximum profit earned is', findMaxProfit(x, y, len(x) - 1)) |
Output:
The maximum profit earned is 25
The time complexity of the above solution is exponential since the code is doing a lot of redundant work. For example, for solving the problem T(n), a recursive call is made to find the maximum profit for both T(n-1) and T(n-2). However, finding the maximum profit for T(n-1) also requires finding the maximum profit for T(n-2). As the recursion grows deeper, more and more of this type of unnecessary repetition occurs.
This repetition can be avoided with dynamic programming. The idea is to cache each time any subproblem T(i) is computed. If we are ever asked to compute it again, return the cached result and not recompute it. The bottom-up approach computes the maximum earnings of all days, using the already computed profit of past days. The maximum earnings T[i] possible till the i'th day can be calculated by taking the maximum of the below actions:
- Sell the first stock on the
i'thday, and add the profit to the maximum earnings till the(i-1)'thday. - Sell the second stock on the
i'thday, and add the profit to the maximum earnings till the(i-2)'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 |
#include <iostream> #include <vector> #include <algorithm> using namespace std; // Function to find the maximum earnings that can be earned by selling the stocks. // Here, arrays `x[0…n-1]` and `y[0…n-1]` contains the two different stocks' // future price predictions for the next n–days. int findMaxProfit(vector<int> const &x, vector<int> const &y) { int n = x.size(); // base case if (n == 0) { return 0; } // Create an auxiliary array `T[]` to save solutions to the subproblems. // Here, `T[i]` stores the maximum earnings till day `i`. int T[n + 1]; // Base cases T[0] = 0; T[1] = max(x[0], y[0]); // Fill the auxiliary array `T[]` in a bottom-up manner for (int i = 2; i <= n; i++) { T[i] = max(x[i - 1] + T[i - 1], y[i - 1] + T[i - 2]); } // `T[n]` stores the maximum earnings till day `n` return T[n]; } int main() { vector<int> x = { 5, 3, 4, 6, 3 }; vector<int> y = { 8, 4, 3, 5, 10 }; cout << "The maximum profit earned is " << findMaxProfit(x, y); return 0; } |
Output:
The maximum profit earned is 25
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 |
class Main { // Function to find the maximum earnings that can be earned by selling the stocks. // Here, arrays `x[0…n-1]` and `y[0…n-1]` contains the two different stocks' // future price predictions for the next n–days. public static int findMaxProfit(int[] x, int[] y) { // base case if (x.length == 0) { return 0; } // create an auxiliary array `T[]` to save solutions to the subproblems. // Here, `T[i]` stores the maximum earnings till day `i`. int[] T = new int[x.length + 1]; // Base cases T[0] = 0; T[1] = Integer.max(x[0], y[0]); // Fill the auxiliary array `T[]` in a bottom-up manner for (int i = 2; i <= x.length; i++) { T[i] = Integer.max(x[i - 1] + T[i - 1], y[i - 1] + T[i - 2]); } // `T[n]` stores the maximum earnings till day `n` return T[x.length]; } public static void main(String[] args) { int[] x = { 5, 3, 4, 6, 3 }; int[] y = { 8, 4, 3, 5, 10 }; System.out.println("The maximum profit earned is " + findMaxProfit(x, y)); } } |
Output:
The maximum profit earned is 25
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 |
# Function to find the maximum earnings that can be earned by selling the stocks. # Here, arrays `x[0…n-1]` and `y[0…n-1]` contains the two different stocks' # future price predictions for the next n–days. def findMaxProfit(x, y): # base case if not x: return 0 # Create an auxiliary array `T[]` to save solutions to the subproblems. # Here, `T[i]` stores the maximum earnings till day `i`. T = [0] * (len(x) + 1) # Base cases T[0] = 0 T[1] = max(x[0], y[0]) # Fill the auxiliary array `T` in a bottom-up manner for i in range(2, len(x) + 1): T[i] = max(x[i - 1] + T[i - 1], y[i - 1] + T[i - 2]) # `T[n]` stores the maximum earnings till day `n` return T[-1] if __name__ == '__main__': x = [5, 3, 4, 6, 3] y = [8, 4, 3, 5, 10] print('The maximum profit earned is', findMaxProfit(x, y)) |
Output:
The maximum profit earned is 25
The time complexity of the above solution is O(n), where n is the total number of given days. The auxiliary space required by the program is O(n) for the auxiliary array and requires no recursion.
Note that the value of T(n) is calculated in constant time using the values of T(n-1) and T(n-2). We can eliminate the need for an auxiliary array by keeping track of only the last two subproblems’ solutions. Following is an efficient implementation in C++, Java, and Python without using an auxiliary array:
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 |
#include <iostream> #include <vector> #include <algorithm> using namespace std; // Function to find the maximum profit that can be earned by selling the stocks. // Here, arrays `x[0…n-1]` and `y[0…n-1]` contains the two different stocks' // future price predictions for the next n–days. int findMaxProfit(vector<int> const &x, vector<int> const &y) { int n = x.size(); // base case if (n == 0) { return 0; } int prev_of_prev = 0; int prev = max(x[0], y[0]); // Find the maximum profit in a bottom-up manner for (int i = 1; i < n; i++) { int curr = max(x[i] + prev, y[i] + prev_of_prev); prev_of_prev = prev; prev = curr; } // `prev` stores the maximum profit gained till day `n` return prev; } int main() { vector<int> x = { 5, 3, 4, 6, 3 }; vector<int> y = { 8, 4, 3, 5, 10 }; cout << "The maximum profit earned is " << findMaxProfit(x, y); return 0; } |
Output:
The maximum profit earned is 25
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 |
class Main { // Function to find the maximum profit that can be earned by selling the stocks. // Here, arrays `x[0…n-1]` and `y[0…n-1]` contains the two different stocks' // future price predictions for the next n–days. public static int findMaxProfit(int[] x, int[] y) { // base case if (x.length == 0) { return 0; } int prev_of_prev = 0; int prev = Integer.max(x[0], y[0]); // Find the maximum profit in a bottom-up manner for (int i = 1; i < x.length; i++) { int curr = Integer.max(x[i] + prev, y[i] + prev_of_prev); prev_of_prev = prev; prev = curr; } // `prev` stores the maximum profit gained till day `n` return prev; } public static void main(String[] args) { int[] x = { 5, 3, 4, 6, 3 }; int[] y = { 8, 4, 3, 5, 10 }; System.out.println("The maximum profit earned is " + findMaxProfit(x, y)); } } |
Output:
The maximum profit earned is 25
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 |
# Function to find the maximum profit that can be earned by selling the stocks. # Here, arrays `x[0…n-1]` and `y[0…n-1]` contains the two different stocks' # future price predictions for the next n–days. def findMaxProfit(x, y): # base case if not x: return 0 prev_of_prev = 0 prev = max(x[0], y[0]) # Find the maximum profit in a bottom-up manner for i in range(1, len(x)): curr = max(x[i] + prev, y[i] + prev_of_prev) prev_of_prev = prev prev = curr # `prev` stores the maximum profit gained till day `n` return prev if __name__ == '__main__': x = [5, 3, 4, 6, 3] y = [8, 4, 3, 5, 10] print('The maximum profit earned is', findMaxProfit(x, y)) |
Output:
The maximum profit earned is 25
The time complexity of the above solution is O(n) and requires O(n) extra space, where n is the total number of given days.
Find maximum profit earned by buying and selling shares any number of times
Find maximum profit earned from at most two stock transactions
Find maximum profit earned from at most `k` stock transactions
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 :)