Maximum Profit With At Most Two Stock Trading Transactions

🙏
জয় শ্রী রাম
🕉

Algorithms and Data Structures: TheAlgorist.com
System Design: DistributedComputing.dev
Low Level Design: LowLevelDesign.io
Frontend Engineering: FrontendEngineering.io

Problem Statement:

Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two transactions.
Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).
Example 1:
Input: prices = [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3. Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.

Example 2:
Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.

Example 3:
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
Example 4:
Input: prices = [1]
Output: 0

Solution:

Finite state machines are a standard tool to model event-based control logic. If a given problem contains different events and depending on which event occurs we can transition from one state to another then it is highly likely that the problem could be solved using Dynamic Programming State Machine approach.

This problem is similar to Max Profit w/ at most 1 Stock Trade Transaction and Max Profit w/ at most K Stock Trade Transactions in that all these problems have restriction(s) on how many transactions could be made at the maximum.
Making zero transaction will also be valid to maximize profit, when the stock prices are in non-increasing order.

We can only be in two states on any given day:

Hold a stock. Let's call the state for such days hasStock state.
Hold no stock. Let's call the state for such days noStock state.

The START state is always noStock state with zero transaction done till then. Once you make a stock purchase you transition to state hasStock with transition# = 1. You cannot go to transaction#2 before completing transaction#1. In order to complete a transaction you need to sell the stock you have bought as part of that transaction. Also, once you are at transaction #N, there is no way going back to Transaction#(N - 1).
In the same transaction there is no way you can transition to hasStock state from noStock state. You can only transition to hasStock state of the next transaction from the noStock state for a given transaction.
Once we reach the noStock state of transaction#2 that completes the second transaction and the process ends there.

The transition from one state to another is depicted in the state machine diagram below. State Machine Diagram:

T_x denotes Transaction#

Recurrence Relation:

Let noStock[i][j] denote the maximum profit achievable when we are in noStock state on day i (one-based index) and we are in transaction #j (one-based index).

Let hasStock[i][j] denote the maximum profit achievable when we are in hasStock state on day i (one-based index) and we are in transaction #j (one-based index).

For noStock state: j = [0,1,2] for this problem since at most two transactions are allowed.
For hasStock state: j = [1,2] for this problem, since at most two transactions are allowed. j != 0 for hasStock state, since it not possible that we made 0 transaction and still ended up having a stock with us.
When transaction# = 0, we can only be in noStock state.

For Transaction #1:

hasStock state can only be reached from hasStock state of day before, for the same transaction, i.e, hasStock[transaction# = currentTransaction#][day = currentDay - 1] (look at the state machine diagram above).

Maximum profit for hasStock state on a given day i can also be achieved by buying a stock on day i. Since this is transaction #1, we do not have any profit yet, since no transaction has been done yet. To buy a stock on day i we will be spending stockPrices[i]. So, hasStock[first_transaction][day = i] = -stockPrices[i]

Since our goal is to maximize profit, we get the below relation


    hasStock[first_transaction][day = i] = Max(hasStock[first_transaction][day = i - 1], -stockPrices[i])

noStock state for a given day i for the first transaction can be reached in from noStock state of day (i - 1) by doing nothing i.e, by making no transaction at all.

noStock state for a given day i for the first transaction can also be reached from hasStock state of day (i - 1) for first transaction, by selling a stock.

This leads to the below relation for first transaction:


noStock[first_transaction][day = i] = Max(noStock[first_transaction][day = i - 1], hasStock[first_transaction][day = i] + stockPrices[i])

Second Transaction: noStock state for second transaction on any given day can be reached in two ways :

From noStock state of day before for second transaction by doing nothing (i.e, making no transaction at all).
From hasStock state of day before for second transaction by selling a stock.

So,


noStock[second_transaction][day = i] = Max(noStock[second-transaction][day = i - 1], hasStock[second_transaction][day = i] + stockPrices[i])

hasStock state for second transaction can be reached by one of two ways:

From noStock state of day before for previous transaction, by purchasing a stock.
From hasStock state for second transaction for the day before, by doing nothing (i.e, making no transaction).

Following the discussion above and the state machine diagram we get the following recurrence relation:


Day# and Transaction# both are zero-based

hasStock[0][i] = Max(hasStock[0][i-1], -stockPrices[i])
noStock[0][i] = Max(noStock[0][i-1], hasStock[0][i] + stockPrices[i])
hasStock[1][i] = Max(hasStock[1][i-1], noStock[0][i] - stockPrices[i])
noStock[1][i] = Max(noStock[1][i-1], hasStock[1][i] + stockPrices[i])

Base Conditions:
On first day, for hasStock state the maximum profit we can get is negative of the stock price on the first day, since we always start first day with zero profit and then spent money (equal to the stock price of first day) to buy a stock.

hasStock[0][0] = -stockPrices with zero-based indices
hasStock[0][0] denotes maximum profit on first day with 1 transaction with one stock in our possession.

noStock[0][0] = 0, since if we are in noStock day at the end of the first day and we are already part of transaction#1, that would mean that we have made a purchase and have also sold it. So profit made = -stockPrices[0] + stockPrices[0] = 0. Since we are buying and selling at the same price, net profit = 0;

noStock[0][1] = 0, since on the end of first day if we are in noStock state and already two transactions have been made, then this would mean we have made two transaction and have purchased and sold as part of first transaction, and have again purchased and sold as part of second transaction. Since all both the purchases and sales have been made at the same price we have made zero profit. Net profit = 0

On the first day, if we have made two transactions and at the end of the day we one stock in our possession then that would mean that we made the first transaction (purchased and then sold at the same stock price) and made zero profit and then bought one stock as part of second transaction.
hasStock[0][1] = 0 - stockPrices[0] = -stockPrices[0]

Return Value:
We can never achieve maximum profit if we hold a stock on the last day. So the return value will be the maximum of profit we get on the last day by being in noStock state transactions done = 2. You might argue and come up with examples where making 0 or 1 transaction would give you the maximum profit and you not need to do any additional transaction(s). But convince yourself that by doing additional unnecessary transactions you won't miss out on getting the maximum profit since any unnecessary additional transaction would yield zero more profit. So by returning the noStock value for maximum transactions (2 in our case) you are also capturing maximum profit achievable from from lesser number of transactions. So for example if 1 transaction gives maximum profit then 2 transactions will also give the same profit. Let's take an example: for the stock prices [5,5,7] you only need to make one transaction, that is buy stock on first day and sell either on second or third day getting maximum profit of 2. However you would get the same maximum profit by doing 2 transactions instead of one. Buy stock on first day and sell on second day. Buy again on second day and sell on third giving you the maximum profit of (7 - 5) + (5 - 5) = 2. Either way you get same result in case we do not need all 2 transactions to achieve maximum profit. Any unnecessary transactions yield 0 profit, that is why we do not see any error in returning noStock result for last day for 2^nd transaction even when maximum profit can be reached by doing 0 or 1 transaction. YOU NEED TO KEEP IN MIND THAT IN EVERY STAGE WE ARE CHOOSING THE MAXIMUM PROFIT FOR noStock and hasStock STATE. That is why we would never get a lesser profit in higher transaction than in a lower transaction since due to optimal substructure property higher transaction values are computed based on lower or same transaction, and at every point of time we take the maximum profit possible.


    Return noStock[day = last day][transactions done = 2]

Java Code:

Python Code:

Space Optimization:

The above code can be further space optimized using the observation that for computing hasStock and noStock values (for both one transaction and two transactions) for day i, all we need are hasStock and noStock values from day (i - 1) for one transaction and two transactions. So all we need are eight variables instead of two arrays of size n, where n = given number of days, giving us O(8) = O(1) space complexity instead of O(2n) = O(n) space complexity.

Java Code:

Python Code:

How would you Compute Optimal Path to maximize result, i.e, the days on which you would actually buy and sell stock(s) in order to maximize profit ?

Our goal now is to find out the days we would be purchasing stocks and the days we would be selling stocks that would maximize the overall profit.

In almost all the DP problems, finding the path that resulted in the optimal result takes little bit more thinking than just computing the optimal value.

It is always a good idea to first design the algorithm to compute the optimal value and then modify the code to find the optimal path. In most cases you would be reusing the logic you implemented to compute the optimal result, to compute the optimal path. We will see that in the below well-commented code.

Thought process involved in the solution:
An important part of this problem is the constraint on maximum number of transaction we can commit. In our case, it is 2.

Let's think backward and start from 2^nd transaction and let's see how we are making progress. We first need to know what is the purchase and selling price for the 2^nd stock. Once we get that we would move to the 1^st stock. The whole code is based on this simple observation.

Now let's take a look at the state machine diagram we have seen earlier in this chapter. From the diagram it can be very easily said that: we sell a stock when we transition to noStock state from hasStock state from day before for same transaction.
We purchase a stock on day i when we transition to hasStock state for transaction x from noStock state of day (i - 1) for transaction (x - 1).
I have made sure the code below is well commented to make the algorithm crystal clear to you. Keep in mind that you are not obliged to make 2 transactions. You can make, 0, 1 or 2 transaction(s), whichever gives you maximum profit.

Java Code:

Python Code:

Login to Access Content

Don't forget to look at the other problems in our State Machine Approach series to have a strong understanding and a good command of this concept:

Instructor:

Abhishek Dey

Senior SDE | Chief Architect

Microsoft | University of Florida

View LinkedIn profile

If you have any feedback, please use this form: https://thealgorists.com/Feedback.