Given a list containing future price predictions of two different stocks for the next n-days, find the maximum profit that can be 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, you 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 top-down manner. To find the maximum profit till n'th day, there are two possible options:
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
40
41
|
#include <stdio.h>
// Utility function to return the maximum of two integers
int max(int i, int j) {
return i > j ? i : j;
}
// 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 future price predictions of the
// two different stocks for the next n-days
int maxProfit(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 = max(profit, x[n] + maxProfit(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] + maxProfit(x, y, n – 2));
// return the maximum profit
return profit;
}
int main()
{
int x[] = { 5, 3, 4, 6, 3 };
int y[] = { 8, 4, 3, 5, 10 };
int n = sizeof(x) / sizeof(x[0]);
printf(“Maximum profit earned is %d”, maxProfit(x, y, n – 1));
return 0;
}
|
Output:
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
|
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 future price predictions of the
// two different stocks for the next n-days
public static int maxProfit(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] + maxProfit(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] + maxProfit(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(“Maximum profit earned is “ + maxProfit(x, y, x.length – 1));
}
}
|
Output:
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
|
# 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 future price predictions of the
# two different stocks for the next n-days
def maxProfit(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] + maxProfit(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] + maxProfit(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(“Maximum profit earned is”, maxProfit(x, y, len(x) – 1))
|
Output:
Maximum profit earned is 25
Download Run Code
Output:
Maximum profit earned is 25
Download Run Code
Output:
Maximum profit earned is 25
Download Run Code
Output:
Maximum profit earned is 25
The above solution’s time complexity 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 sub-problem T(i) is computed. If we are ever asked to compute it again, return the cached result and not recompute it. The following 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:
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 <stdio.h>
// Utility function to return the maximum of two integers
int max(int i, int j) {
return i > j ? i : j;
}
// 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 future price predictions
// of the two different stocks for the next n-days
int maxProfit(int x[], int y[], int n)
{
// 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 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()
{
int x[] = { 5, 3, 4, 6, 3 };
int y[] = { 8, 4, 3, 5, 10 };
int n = sizeof(x) / sizeof(x[0]);
printf(“Maximum profit earned is %d”, maxProfit(x, y, n));
return 0;
}
|
Output:
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
|
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 future price predictions
// of the two different stocks for the next n-days
public static int maxProfit(int[] x, int[] y)
{
// 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 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(“Maximum profit earned is “ + maxProfit(x, y));
}
}
|
Output:
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
|
# 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 future price predictions
# of the two different stocks for the next n-days
def maxProfit(x, y):
# 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 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(“Maximum profit earned is”, maxProfit(x, y))
|
Output:
Maximum profit earned is 25
Download Run Code
Output:
Maximum profit earned is 25
Download Run Code
Output:
Maximum profit earned is 25
Download Run Code
Output:
Maximum profit earned is 25
The time complexity of the above solution is O(n). The auxiliary space used 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). The need for an auxiliary array can be eliminated by keeping track of only the last two subproblems’ solutions. Following is a better 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
|
#include <stdio.h>
// Utility function to return the maximum of two integers
int max(int i, int j) {
return i > j ? i : j;
}
// 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 future price predictions
// of the two different stocks for the next n-days
int maxProfit(int x[], int y[], int n)
{
// Base cases
int prev_of_prev = 0;
int prev = max(x[0], y[0]);
// Find the maximum profit in 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()
{
int x[] = { 5, 3, 4, 6, 3 };
int y[] = { 8, 4, 3, 5, 10 };
int n = sizeof(x) / sizeof(x[0]);
printf(“Maximum profit earned is %d”, maxProfit(x, y, n));
return 0;
}
|
Output:
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
|
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 future price predictions
// of the two different stocks for the next n-days
public static int maxProfit(int[] x, int[] y)
{
// Base cases
int prev_of_prev = 0;
int prev = Integer.max(x[0], y[0]);
// Find the maximum profit in 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(“Maximum profit earned is “ + maxProfit(x, y));
}
}
|
Output:
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
|
# 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 future price predictions
# of the two different stocks for the next n-days
def maxProfit(x, y):
# Base cases
prev_of_prev = 0
prev = max(x[0], y[0])
# Find the maximum profit in 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(“Maximum profit earned is”, maxProfit(x, y))
|
Output:
Maximum profit earned is 25
Download Run Code
Output:
Maximum profit earned is 25
Download Run Code
Output:
Maximum profit earned is 25
Download Run Code
Output:
Maximum profit earned is 25
The time complexity of the above solution is O(n) and auxiliary space used by the program is O(1).