🙏

জয়  শ্রী  রাম

🕉

---

Problem Statement:

Say you have an array prices for which the i^th element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).
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: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4. Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Example 2:
Input: [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: [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.

Before going into detailed discussion I would like to bring to your attention that: even though the problem statement says that you can make as many transactions as you want it won't be logical to make more than N number of transactions where N = total number of days. Since there is no gain in doing more than one transaction in a day, since if you buy and sell on the same day you are making 0 profit. Convince yourself.

Every day we can be one of these two states:

• either we have a stock with us. Let's call this state hasStock state.
• or, we have no stock with us. Let's call this state noStock state.

Transition:
noStock state transitions to hasStock state by buying a stock.
hasStock state transitions to noStock state by selling the purchased stock.

noStock is also the START state, because on day-1 (first day) we start with a clean slate (no stock with us). Since we can make as many transactions as we want, this transitions can go on happening as many times as we want, keeping in mind that

• we cannot buy a stock before selling the one we already have with us.
• our goal is to maximize profit.

This leads us to the state machine diagram below.

State Machine Diagram:



Please subscribe to access the State Machine Diagram.
After subscribing please come back and refresh this page.

Recurrence Relation:

Let noStock[i] denote the maximum profit achievable at the end of day i if we have no stock with us on day i.

Let hasStock[i] denote the maximum profit achievable at the end of day i if we have a stock with us on day i.

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

Return value: Since our goal is to maximize the profit we can never end the last day with a stock being held, because that would be waste of money that we bought a stock but did not sell it on or before the last day. So the return value would always be noStock[lastDay].

Base Condition(s):

noStock[0] = 0
hasStock[0] = -stockPrices[0]

We get the above base cases using the below logic:

• Ending the day with no stock being hold means we did not make any transaction. We started the day with no stock and ended the day with no stock. So net profit = 0;
  noStock[0] = 0
• If we end the first day with a stock being held that would mean that we started the day with 0 profit and then spent stockPrices[0] to buy a stock where stockPrices[0] is the price of stock on the first day.
  hasStock[0] = -stockPrices[0]

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.

The above discussion leads us to the below space optimized code:

Java Code:

Login to Access Content

Python Code:

Login to Access Content




The below code shows how we got to the space optimized code from the original code (non-space-optimized one):

Java Code:

Login to Access Content

Python Code:

Login to Access Content

Find the Days to Buy and Sell the Stocks to Maximize Profit for the above problem:

Our goal now is to print the days we would be purchasing a stock and the days 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 days and selling days 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 the solution:

• Using the same states we have been using so far, it is very easily understandable from the State Machine Diagram that if we reach noStock state on day i from hasStock state of day (i - 1), then that would mean that we sold a stock on day i.
  
  But a very important observation should be made here:
  let's say the stock prices for 5 days look like this : [1, 2, 3, 4, 5] , i.e, when the stock price soars. Starting from day-2 everyday we would think that today is the best day to sell since everyday we have better stock rate than day before. And starting from day-2 everyday we would transition to noStock state from hasStock (of day before). Try to convince this to yourself by working on this example. So, we cannot just go on adding a day to the sellingDay list just because we transitioned to noStock state from hasStock state. A very easy way to know when this scenario occurs is to see if all the already gotten purchase days and selling days are in pairs. Which means we would have more selling days in our list than the purchase days. But this is invalid since a selling day would always have a corresponding purchase day.The solution here is: if we see we are breaking the constraint that number of selling days cannot be more than total number of purchase days, we would know that this is the case where stock price is going up and we just got a better day to sell the last purchased stock. So remove the last stock selling day, and add the current day.
• If we transition to hasStock state from noStock on day i then day i is a purchase day. But if stock rate is declining like in [5, 4, 3, 2, 1] then everyday would prove to be a purchase day. In such scenario we need to remove the last purchase day and add the current as updated purchase day. It is very easy to detect such scenario: If we see that we already have more purchase days than selling days we would know that we are in a situation when stock prices is declining giving us better day for stock purchase.

Java Code:

Please subscribe to access the code for computing Optimal DP Path.
After subscribing please come back and refresh this page.

Python Code:

Please subscribe to access the code for computing Optimal DP Path.
After subscribing please come back and refresh this page.




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/ at most 1 Stock Trade Transaction

Instructor: