Maximum Profit With At Most K Stock Trading Transactions

Get started

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

Problem Statement:

Say you have an array 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 at most k transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
Example 1:
Input: [2,4,1], k = 2
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.
Example 2:
Input: [3,2,6,5,0,3], k = 2
Output: 7
Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4. Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.

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.

In the given problem, 0 to maximum of K transactions are allowed. A transaction consists of first buying a stock and then selling it. Our goal is to maximize profit. We would make zero transaction to maximize profit when the prices of the stock are in non-increasing order, for example, [10, 10, 9, 6, 5, 5, 4, 1].

Right after reading the problem statement, the thing that strikes our mind is that there are two states involved in this problem. (1) Either we buy a stock and hold a stock. Let's call this state hasStock. Or, (2) we sell the purchased stock and end up with no stock. Let's call this state noStock state. With every state day and transaction# are associated (state for which day and how many transactions made till then).

The START state is always noStock state on first day with transaction# = 0.
From START state we have two options:

do nothing and be in same noStock state.
buy a stock and transition to hasStock state with transaction# = 1. The associated day will be the day on which we buy the stock.

Once we buy the first stock we again have two options:

do nothing and be in same hasStock state.
sell the stock and transition to noStock state as part of the same transaction. The associated day will be the day on which we sell the stock.

Thw above whole observation is very important as this will help us in extrapolating the transition behavior for all K transactions and for all days, and eventually will help us coming up with the state machine diagram.

If we think through end-to-end now, below would be our observation:

For every transaction, the transaction starts with buying a stock i.e, hasStock state, and from there we can transition to noStock state by selling the stock we bought as part of this transaction. For a specific transaction there is no way we can transition to hasStock state from noStock state, because buying a stock would take us to next transition. Which means, we can transition to hasStock state for transaction# i from noStock state for transaction# (i - 1). This is not true only for transaction# 0, since in transaction# 0 we only have one state and that is noStock state and this state persists till we buy our first stock.

The above discussion leads us to the below state machine diagram.

State Machine Diagram:

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

Code:

Please see the comments in the code below where I have explained the whole implementation logic in details:

Java Code:

Python Code:

Same Solution But Little Bit More Concise:

Java Code:

Python Code:

Space Optimization:

Look at the above code how during the computation for day i we ony need to know noStock and hasStock values for all k transactions for day (i - 1). This observation optimizes the space complexity from O(no_of_days * k) to O(k). This observation proves that a 2D array is unnecessary and an 1D array should suffice as we will see in the code below:

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. It might in fact make the problem of computing optimal path for the above problem seem a little bit convoluted for some.

Let's think backward and start from k^th transaction and let's see how we are making progress. We first need to know what is the purchase and selling price for the k^th stock. Once we get that we would move to the (k - 1)-th stock and so on all the way till the first 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 all k transactions. If you think you do not need this many transactions to maximize profit, you are free to make less than k transaction. You would make 0 transaction if stock price never goes up, like [6, 5, 5, 4, 2, 2].

Java Code:

Please subscribe to access the Code to Compute Optimal Path.
After subscribing please come back and refresh this page.

Python Code:

Please subscribe to access the Code to Compute Optimal 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:

Instructor:

Abhishek Dey

Senior SDE | Chief Architect

AWS | Microsoft | University of Florida

View LinkedIn profile