Maximum Profit with at most one stock trading transaction allowed
A simple application of Dynamic Programming

Customer Support: admin@thealgorists.com

Feedback:
We are listening to your every feedback,
and taking action to constantly improve your learning experience.
If you have any feedback, please use this form:
https://thealgorists.com/Feedback.
 If you are a student, email to admin@thealgorists.com to get special student discount.
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 = 61 = 5. Not 71 = 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 eventbased 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:
 hasStock
 noStock
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 nonzero 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])
Code:
class Solution {
public int maxProfit(int[] prices) {
int days = prices.length;
if (prices == null  days < 2) {
return 0;
}
int[] hasStock = new int[days]; // hasStock[i] = max profit we can have at the end of day i with
// one stock in possession, following the transition relation in
// the state machine diagram
int[] noStock = new int[days]; // noStock[i] = max profit at the end of day i with no stock at hand
// following the transition relation in the state machine diagram
// Base Condition
hasStock[0] = prices[0]; // we need to have one stock in our possession mandatorily
noStock[0] = 0; // on first day there is no stock to sell. So, noStock[0] means
// we did not make any transaction at all on the first day
// giving us 0 net profit
for (int day = 1; day < days; day++) {
hasStock[day] = Math.max(hasStock[day  1], prices[day]);
noStock[day] = Math.max(noStock[day  1], hasStock[day  1] + prices[day]);
}
return noStock[days  1];
}
}
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.
class Solution {
// SPACE OPTIMIZATION
public int maxProfit(int[] prices) {
int days = prices.length;
if (prices == null  days < 2) {
return 0;
}
/*
We have room for Space Optimization here 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.
*/
int previousDayHasStockValue = 0; // int[] hasStock = new int[days];
int previousDayNoStockValue = 0; // int[] noStock = new int[days];
// Base Condition
previousDayHasStockValue = prices[0]; // hasStock[0] = prices[0];
previousDayNoStockValue = 0; // noStock[0] = 0;
int currentDayHasStockValue = 0;
int currentDayNoStockValue = 0;
for (int day = 1; day < days; day++) {
currentDayHasStockValue = Math.max(previousDayHasStockValue, prices[day]); // hasStock[day] = Math.max(hasStock[day  1], prices[day]);
currentDayNoStockValue = Math.max(previousDayNoStockValue, previousDayHasStockValue + prices[day]); // noStock[day] = Math.max(noStock[day  1], hasStock[day  1] + prices[day]);
previousDayHasStockValue = currentDayHasStockValue;
previousDayNoStockValue = currentDayNoStockValue;
}
return previousDayNoStockValue;
}
}
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 wellcommented 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 nonzero nonnegative profit.
class Solution {
public int maxProfit(int[] prices) {
int days = prices.length;
if (prices == null  days < 2) {
return 0;
}
int previousDayHasStockValue = prices[0];
int previousDayNoStockValue = 0;
int currentDayHasStockValue = 0;
int currentDayNoStockValue = 0;
int purchaseDay = 0; // initialize purchaseDay with first day
int saleDay = 1;
int tempPurchaseDay = 0;
for (int day = 1; day < days; day++) {
currentDayNoStockValue = Math.max(previousDayNoStockValue, previousDayHasStockValue + prices[day]);
if (currentDayNoStockValue > previousDayNoStockValue) {
purchaseDay = tempPurchaseDay;
saleDay = day;
}
currentDayHasStockValue = Math.max(previousDayHasStockValue, prices[day]);
if (currentDayHasStockValue > previousDayHasStockValue) {
tempPurchaseDay = day;
}
previousDayHasStockValue = currentDayHasStockValue;
previousDayNoStockValue = currentDayNoStockValue;
}
if (saleDay != 1) { // saleDay == 1 means we did not get a chance to sell the purchased stock, example: where
// stock price is going down or staying constant like [5,4,4,3,3,2,1]
System.out.println((purchaseDay + 1)+ " > " + (saleDay + 1)); // added 1 since days were 0based index
}
return previousDayNoStockValue;
}
}
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
The above content is written by:
Abhishek Dey
A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More
Microsoft  University of Florida
If you have any feedback, please use this form: https://thealgorists.com/Feedback.
Follow Us On LinkedIn