It is a relatively nice day in the Twin Cities of Minneapolis and St. Paul.
This weekend my wife and I will go to visit our younger son. His house is about three hours by car. It does not make sense to fly. It will take longer than driving when you consider the overhead at the airports.
I continue giving it a try to the process to solve dynamic problems using some simple steps as described in the paper Dynamic programming is simple by omgitspavel. Each time I give it a try I add additional guidance.
The main problem that I see with the approach is that one still has to read, understand and explore other methods before diving into dynamic programming. The problem we will be solving in this post can be resolved faster and better not using dynamic programming.
The problem at hand is LeetCode 122 Best Time to Buy and Sell Stock II which is rated Medium.
If interested in the problem I suggest you go to the LeetCode web site and read the requirements. Not sure if they change with time.
You are given an integer array prices where prices[i] is the price of a given stock on the ith day. On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day. Find and return the maximum profit you can achieve. Constraints: o 1 <= prices.length <= 3 * 104 o 0 <= prices[i] <= 104 Related Topics: o Array o Dynamic Programming o Greedy
We are given an int[] of prices which indicate the price of a particular stock in a specified set of consecutive days. We are supposed to compute the maximum profit that we can achieve by purchasing and then selling stock on different days.
Note that in the Related Topics section dynamic programming is listed.
We are going to solve this problem using the Java programming language and the VSCode IDE on a Windows platform. We will not be using the on-line IDE provided by LeetCode. Due to this fact, we will have to develop a simple test scaffold which should be able to read the input line, populate an array, call the function of interest and display the output. Note that this code IS NOT PART OF THE SOLUTION.
public int maxProfit(int[] prices) {
}
This code snippet illustrates the signature of the function of interest.
7,1,5,3,6,4 main <<< prices: [7, 1, 5, 3, 6, 4] main <<< Output: 7 main <<< Output: 7 1,2,3,4,5 main <<< prices: [1, 2, 3, 4, 5] main <<< Output: 4 main <<< Output: 4 7,6,4,3,1 main <<< prices: [7, 6, 4, 3, 1] main <<< Output: 0 main <<< Output: 0 1,3,2,8,4,9 main <<< prices: [1, 3, 2, 8, 4, 9] main <<< Output: 13 main <<< Output: 13 3,5,9,2,11 main <<< prices: [3, 5, 9, 2, 11] main <<< Output: 15 main <<< Output: 15
We are provided with a single input line that holds the prices for the stock in consecutive days.
Our test scaffold seems to read the input line, populate the prices int[] and then display the contents of the prices array. This is done in order to make sure that all is well so far.
Our test scaffold seems to be invoking two implementations of the function of interest. Both implementations seem to return the same result.
/**
* Test scaffold
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read int[] with pricess ****
int[] prices = Arrays.stream(br.readLine().trim().split(","))
.mapToInt(Integer::parseInt)
.toArray();
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< prices: " + Arrays.toString(prices));
// **** call function of interest and display output ****
System.out.println("main <<< Output: " + maxProfitDP(prices));
// **** call function of interest and display output ****
System.out.println("main <<< Output: " + maxProfit(prices));
}
Our test scaffold seems to follow closely the description we covered while going over the test cases. I do not have anything to add at this time.
// **** memoization ****
static private HashMap<String, Integer> memo = null;
// ???? ????
// static private int dpCalls = 0;
// static private HashMap<String, Integer> dpArgs = null;
We declare a HashMap `memo` which will be used to hold information in order to avoid multiple calls to the recursive function named `dp()`. This is quite typical in dynamic problems.
The other two variables are used to collect some execution data. At this time both variables have been commented out. If interested you should be able to uncomment code and get additional information about the execution of the recursive call which we will be looking at shortly.
/**
* Find and return the maximum profit you can achieve.
*
* 1. Produce a bruteforce solution.
* 2. Come up with the idea of what do we do on each step.
* 3. Write the recurrent relation in form of recursion.
* 4. Add a base case.
* 5. Calculate the correct value to return.
*
* 200 / 200 test cases passed.
* Status: Accepted
* Runtime: 60 ms
* Memory Usage: 60.4 MB
*/
static public int maxProfitDP(int[] prices) {
// **** initialization ****
int maxProfit = 0;
memo = new HashMap<>();
// ???? ????
// dpCalls = 0;
// dpArgs = new HashMap<>();
// **** first day no stock purchased ****
maxProfit = dp(prices, 0, false);
// ???? ????
// System.out.println("maxProfitDP <<< dpCalls: " + dpCalls);
// System.out.println("maxProfitDP <<< dpArgs: " + dpArgs.toString());
// System.out.println("maxProfitDP <<< dpArgs.size: " + dpArgs.size());
// **** return max profit ****
return maxProfit;
}
This is an implementation of the problem using the process described in the paper previously mentioned. Some of the steps are indicated in the comment section of the function.
In a nutshell we need to initialize memoization, start the recursive process which will return the max profit. At that point we just need to return it to be displayed by the caller.
The commented code is used to get additional insights into the execution of the recursive call.
/**
* Recursive dynamic programming function.
* Uses memoization.
*/
static private int dp(int[] prices, int day, Boolean bought) {
// **** base case ****
if (day == prices.length) return 0;
// **** generate key ****
String key = "" + day + "," + (bought ? "1" : "0");
// ???? ????
// System.out.println("dp <<< key ==>" + key + "<==");
// **** check memoization ****
if (memo.containsKey(key)) return memo.get(key);
// ???? ????
// dpCalls++;
// **** initialization ****
int maxProfit = 0;
// **** buy stock (step 1) ****
if (!bought)
maxProfit = Math.max(maxProfit, dp(prices, day + 1, true) - prices[day]);
// **** sell stock (step 2) ****
if (bought)
maxProfit = Math.max(maxProfit, dp(prices, day + 1, false) + prices[day]);
// **** do nothing (step 3) ****
maxProfit = Math.max(maxProfit, dp(prices, day + 1, bought));
// ???? ????
// System.out.println("dp <<< day: " + day + " bought: " + bought + " maxProfit: " + maxProfit);
// Integer val = dpArgs.get(key);
// System.out.println("dp <<< val: " + val);
// if (val == null)
// dpArgs.put(key, 1);
// else
// dpArgs.put(key, val + 1);
// **** update memoization ****
memo.put(key, maxProfit);
// **** return max profit ****
return maxProfit;
}
We start by defining a base case in order to be able to end recursion.
We generate a key using the `day` and `bought` values. Since we cannot have two separate keys in a HashMap, we will combine then into a string.
We will then check memoization to avoid recursive calls. If we do not find the specified key, we will generate the value, update our memoization, and return the value to the caller.
In this problem we can define three cases. Each case requires a recursive call and additional data that accommodates the specifics of each state. Please take a look at the code and make sure you follow what is going on.
When all is said and done with recursion, we save the result in the memoization data structure and return the max profit value.
If you go back to the entry point for this function, you can see that the solution was accepted by LeetCode but it is not as fast as we would expect. Perhaps there is a better approach.
/**
* Find and return the maximum profit you can achieve.
*
* 200 / 200 test cases passed.
* Status: Accepted
* Runtime: 0 ms
* Memory Usage: 38.3 MB
*
* Execution: O(n) - Space: O(1)
*/
static public int maxProfit(int[] prices) {
// **** initialization ****
int maxProfit = 0;
// **** traverse the prices array ****
for (int day = 1; day < prices.length; day++) {
// **** today's profit ****
int profit = prices[day] - prices[day - 1];
// **** update the max profit (if needed) ****
if (profit > 0)
maxProfit += profit;
}
// **** return the max profit ****
return maxProfit;
}
This implementation of the function of interest does not make use of dynamic programming.
We start by initializing the `maxProfit` variable to indicate we have not sold stock yet.
We the traverse the prices int[] array. We compute the profit we would make if we purchase the stock yesterday and sell it today.
If the `profit` is positive, that indicates we would make a profit if we sell our stock today. The `maxProfit` is updated and the process repeats.
When all is said and done we return the value in the `maxProfit` variable.
Take a look at the comments section. This solution is quite fast compared with the one implemented using dynamic programming. When looking for an approach to solve a problem, take time and ask questions to make sure you have the best possible approach in the allotted time.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
Please note that the code here presented might not be the best possible solution. In most cases, after solving the problem, you can take a look at the best accepted solution provided by the different web sites (i.e., HackerRank, LeetCode).
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.
Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.
Regards;
John