🙏

জয়  শ্রী  রাম

🕉

---

Problem Statement:

Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Note that you cannot sell a stock before you buy one.
Example 1:
Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5. Not 7-1 = 6, as selling price needs to be larger than buying price.
Example 2:
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 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.

Even though this is a pretty easy problem, drawing the Machine State Diagram for this one might need some thinking.
If you have already gone through the other 5 similar problems on Stocks demonstrating application of Machine State Approach of Dynamic Programing, then you can very easily figure out that there are two distinct states involved in this problem:

1. hasStock
2. noStock

Now, since we can make only one transaction we would have two different kind of noStock situation here. One is noStock situation when it is pristine, that is on the first day when we start with no stock at hand and this pristine state continues till we buy a stock, and then the state transitions to hasStock. Now the second noStock situation arises when we sell the stock we bough. Now, how is this noStock situation different from the pristine noStock situation ? The difference is that, since we are allowed to make only one transaction, we cannot transition to hasStock state from the second noStock state, but we can transition to hasStock state from pristine noStock state.

So need a start state or initial state. This start state or initial state persists till we buy a stock and transition to hasStock state. This transition can happen on the first day , or on the last day or any day in between or never at all (if the stock price goes downhill, think of this test case [9, 7, 6, 5, 5, 5, 2]. In this case you would make no transaction at all since buying a stock on any of these days won't give you positive non-zero profit irrespective of which day you decide to sell the stock).
And then we need noStock state which would indicate that we have sold the purchased stock.

Once we have figured this whole thing out, coming up with the state machine diagram won't be very hard.
State Machine Diagram:

DP Relation:

Let hasStock[i] denote the maximum profit obtainable at the end of day i when we hold a stock.
Let noStock[i] denote the maximum profit achievable at the end of day i with no stock in hand.

Since hasStock[i] would always be negative, since we started with zero profit and then we are spending money to buy a stock. This would mean that we would always want to buy the stock on the day d, such as d <= i, on which the stock price was minimum among all days [0...i].
This leads us to the DP relation below:

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

Java Code:

Login to Access Content

Python Code:

Login to Access Content

Space Optimization:

In the above code, we have room for Space Optimization because we do NOT need the hasStock[] and noStock[] arrays due to our below observation:

• In the for loop notice that for every day = i we are relying on hasStock[i - 1] and hasStock[i - 1].
  At no point of time we are using anything more than that and so having the whole array in memory is adding no value when we are dependent on just these two values
  So what we can do is we can take two variables that would hold the value of noStock[i - 1] and hasStock[i - 1] when we are processing for day = i.
  We would also need two variables to hold noStock and hasStock values for the current day we are computing for.

Java Code:

Login to Access Content

Python Code:

Login to Access Content

How to print the Optimal DP Path ?

Our goal now is to print the day we would be purchasing a stock and the day we would be selling the stock that would maximize the 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. For our case, it would be finding the purchase day and selling day that led us to get the maximum profit.

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 need 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 solving the problem:

To compute the days for purchase and sell that would give maximum profit the thought process is as follows:

• If on any day we get better profit than the day before for hasStock state, that day would be a potential purchase day. But we will have to keep in mind that even though the current day is giving better profit does not mean that this current day will be the day that would bring the maximum profit for us (think about the concept of local maxima and global maxima). So we will have to keep a variable tempPurchaseDay that would store the day whenever we get better profit for hasStock state. Whether the tempPurchaseDay brings the maximum profit so far or not will be determined while computing profit for current day for noStock state.
• If on day i we get better profit than the day before for noStock state, then that would mean that selling the stock on that day would give the most profit till day i. So we would replace the last saleDay with day i and assign tempPurchaseDay as purchaseDay since tempPurchaseDay represents the most profitable day to buy stock till day i.
• If we see that we did not get a sale day at the end, then that would mean that the stock price never went up after the first day. So we did not get a chance to sell in order to get non-zero non-negative profit.

Java Code:

Login to Access Content

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:

• Stock Trading With Cooldown
• Stock Trading With Transaction Fee
• Max Profit w/ at most 2 Stock Trade Transactions
• Max Profit w/ at most K Stock Trade Transactions
• Max Profit w/ Unlimited Stock Trade Transactions

Instructor: