Find maximum profit earned from at most two stock transactions

Given a list containing future predictions of share prices, find the maximum profit earned by buying and selling shares at most twice with a constraint that a new transaction can only start after the previous transaction complete, i.e., we can only hold at most one share at a time.

For example,

Input: Stock prices are {2, 4, 7, 5, 4, 3, 5}
Output: The maximum profit is 7

Buy at a price 2 and sell at a price 7
Buy at a price 3 and sell at a price 5

Input: Stock prices are {10, 6, 8, 4, 2}
Output: The maximum profit is 2

Buy at a price 6 and sell at a price 8

Input: Stock prices are {8, 7, 6, 4}
Output: The maximum profit is 0

Buying and selling stock will result in loss

Practice this problem

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 k times, 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.

Here, we are allowed to stock shares at most twice. The idea is to use extra space to solve this problem. We create an auxiliary array profit[] and fill it while performing two scans of the input array, which contains the stock price information for each day.

In the first scan, update profit[i] to the maximum profit earned by a single stock transaction from the day i till day n-1. We can do this by traversing the array from right to left and keeping track of the maximum stock price seen so far.
In the second scan, update profit[i] by taking a maximum of profit[i-1] (i.e., maximum profit calculated so far), and the total profit obtained by closing the first transaction on the day i and performing another transaction from the day i till day n-1. We can find the maximum profit earned on a stock transaction closing on the day i by traversing the array from left to right and keeping track of the minimum stock price seen so far.

Finally, the last element of profit[] has the result.

Note that we can initiate the second transaction on the same day as closing the first transaction, i.e., at the same price. This does not violate the problem constraint that a second transaction can only start once the first transaction is complete. This essentially means that we have performed only a single transaction.

The algorithm can be implemented as follows in C++, Java, and Python:

C++

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

// Function to find the maximum profit earned from at most two stock transactions

int findMaxProfit(vector<int> const &price)

{

int n = price.size();

// base case

if (n == 0) {

return 0;

}

// create an auxiliary array of size `n`

int profit[n];

// initialize the last element of the auxiliary array to 0

profit[n-1] = 0;

// to keep track of the maximum stock price on the right of the current stock price

int max_so_far = price[n - 1];

// traverse the array from right to left

for (int i = n - 2; i >= 0; i--)

{

// update profit[i] to the maximum profit earned by a single stock

// transaction from the day `i` till day `n-1`

profit[i] = max(profit[i + 1], max_so_far - price[i]);

// update maximum stock price seen so far

max_so_far = max(max_so_far, price[i]);

}

// to keep track of the minimum stock price to the left of the current stock price

int min_so_far = price[0];

// traverse the array from left to right

for (int i = 1; i < n; i++)

{

/* Update profit[i] by taking a maximum of the following:

1. profit[i-1], which represents the maximum profit calculated so far

2. The total profit obtained by closing the first transaction on the day `i`

and performing another transaction from the day `i` till day `n-1`. */

profit[i] = max(profit[i - 1], (price[i] - min_so_far) + profit[i]);

// update the minimum stock price seen so far

min_so_far = min(min_so_far, price[i]);

}

// the last element of `profit[]` stores the result

return profit[n - 1];

}

int main()

{

vector<int> price = { 2, 4, 7, 5, 4, 3, 5 };

cout << "The maximum profit is " << findMaxProfit(price);

return 0;

}

Download Run Code

Output:

The maximum profit is 7

Java

class Main

{

// Function to find the maximum profit earned from at most two stock transactions

public static int findMaxProfit(int[] price)

{

int n = price.length;

// base case

if (n == 0) {

return 0;

}

// create an auxiliary array of size `n`

int[] profit = new int[n];

// initialize the last element of the auxiliary array to 0

profit[n - 1] = 0;

// to keep track of the maximum stock price on the right of the current

// stock price

int max_so_far = price[n - 1];

// traverse the array from right to left

for (int i = n - 2; i >= 0; i--)

{

// update profit[i] to the maximum profit earned by a single stock

// transaction from the day `i` till day `n-1`

profit[i] = Math.max(profit[i + 1], max_so_far - price[i]);

// update maximum stock price seen so far

max_so_far = Math.max(max_so_far, price[i]);

}

// to keep track of the minimum stock price to the left of the current

// stock price

int min_so_far = price[0];

// traverse the array from left to right

for (int i = 1; i < n; i++)

{

Update profit[i] by taking a maximum of the following:

1. profit[i-1], which represents the maximum profit calculated so far

2. The total profit obtained by closing the first transaction on the

day `i` and performing another transaction from the day `i`

till day `n-1`.

profit[i] = Math.max(profit[i - 1], (price[i] - min_so_far) + profit[i]);

// update the minimum stock price seen so far

min_so_far = Math.min(min_so_far, price[i]);

}

// the last element of `profit[]` stores the result

return profit[n - 1];

}

public static void main(String[] args)

{

int[] price = { 2, 4, 7, 5, 4, 3, 5 };

System.out.println("The maximum profit is " + findMaxProfit(price));

}

Download Run Code

Output:

The maximum profit is 7

Python

# Function to find the maximum profit earned from at most two stock transactions

def findMaxProfit(price):

n = len(price)

# base case

if n == 0:

return 0

# create an auxiliary space of size `n`

profit = [0] * n

# initialize the last element of the auxiliary space to 0

profit[n - 1] = 0

# to keep track of the maximum stock price on the right of the current stock price

max_so_far = price[n - 1]

# traverse the list from right to left

for i in reversed(range(n - 1)):

# update profit[i] to the maximum profit earned by a single stock

# transaction from the day `i` till day `n-1`

profit[i] = max(profit[i + 1], max_so_far - price[i])

# update maximum stock price seen so far

max_so_far = max(max_so_far, price[i])

# to keep track of the minimum stock price to the left of the current stock price

min_so_far = price[0]

# traverse the list from left to right

for i in range(1, n):

''' Update profit[i] by taking a maximum of the following:

1. profit[i-1], which represents the maximum profit calculated so far

2. The total profit obtained by closing the first transaction on the day `i`

and performing another transaction from the day `i` till day `n-1`. '''

profit[i] = max(profit[i - 1], (price[i] - min_so_far) + profit[i])

# update the minimum stock price seen so far

min_so_far = min(min_so_far, price[i])

# the last element of profit stores the result

return profit[n - 1]

if __name__ == '__main__':

price = [2, 4, 7, 5, 4, 3, 5]

print('The maximum profit is', findMaxProfit(price))

Download Run Code

Output:

The maximum profit is 7

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 from at most two stock transactions

C++

Java

Python

Share this: