Good morning! Hope your day has started well. As expected for this season, days are getting cooler. That said we have not experienced freezing temperatures (< 32 F) in the Twin Cities area of Minneapolis and St. Paul yet. The forecast for tomorrow calls for a low of 30 F. In the near future we will find out if the forecast is accurate.
Yesterday it rained on and off most of the day. Around noon we had some thunderstorms and later in the afternoon it repeated. As you might already know, I tend to shutdown all computers at home during thunderstorms. I had lost a few pieces of computer equipment before I set a policy of turning off computer equipment when the weather is acting up. Yesterday, after shutting down my main computer, I decided to install the Uninterruptible Power Supply that I purchased a month or so ago. It took me about 15 minutes moving, cleaning, installing, and verifying the operation of the UPS.
I continue to read the book Intro to Python for Computer Science and Data Science: Learning to Program with AI, Big Data and The Cloud by Paul Deitel and watching the on-line video Python Fundamentals by the same author. I am experimenting with exercises from the course and book. I have to admit that one of the best ways to learn is to read and experiment.
I am also looking for dynamic programming problems and attempting to apply the contents of the article Dynamic programming is simple by omgitspavel. After this post which is catalogued as a dynamic programming, will attempt to solve a set of programs from LeetCode starting with some rated Easy and moving up to the ones rated Hard. I will try covering 15 problems in the next few days.
OK, let’s get down to the problem at hand which is LeetCode 309 Best Time to Buy and Sell Stock with Cooldown rated Medium by LeetCode.
To be honest with you, I tried sticking to the process described by omgitspavel, but since it is a process I diverted a few times and ended with a couple solutions that we will cover shortly.
You are given an array prices where prices[i] is the price of a given stock on the ith day. Find the maximum profit you can achieve. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times) with the following restrictions: o After you sell your stock, you cannot buy stock on the next day (i.e., cooldown one day). Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again). Constraints: o 1 <= prices.length <= 5000 o 0 <= prices[i] <= 1000 Related Topics: o Array o Dynamic Programming
As with so many similar programs, we need the maximize profit buying and selling stock with different caveats. In this case we need to deal with a one-day cooldown period after selling the stock.
We are going to attempt solving this problem using the Java programming language and the VSCode IDE on a Windows computer. For this reason we will not use the on-line IDE provided by LeetCode. We will need to develop a test scaffold which will read the input line, populate the associated array, call the function of interest and display the result. Such code IS NOT PART OF THE SOLUTION.
public int maxProfit(int[] prices) {
}
The signature for the function of interest is simple. We are provided with an array with the stock prices and we need to return the maximum profit.
1,2,3,0,2 main <<< prices: [1, 2, 3, 0, 2] maxProfit0 <<< dp: day: 0 [0, -1] day: 1 [1, -1] day: 2 [2, -1] day: 3 [0, 0] day: 4 [0, 0] maxProfit0 <<< dp: day: 0 [0, -1] day: 1 [1, -1] day: 2 [2, -1] day: 3 [2, 1] day: 4 [0, 0] maxProfit0 <<< dp: day: 0 [0, -1] day: 1 [1, -1] day: 2 [2, -1] day: 3 [2, 1] day: 4 [3, 1] main <<< output: 3 maxProfit <<< day: 1 cost: -1 profit: 1 maxProfit: 0 maxProfit <<< day: 2 cost: -1 profit: 2 maxProfit: 1 maxProfit <<< day: 3 cost: 1 profit: -1 maxProfit: 2 maxProfit <<< day: 4 cost: 1 profit: 3 maxProfit: 2 main <<< output: 3 1 main <<< prices: [1] main <<< output: 0 main <<< output: 0 5,2,4,6,1,3 main <<< prices: [5, 2, 4, 6, 1, 3] maxProfit0 <<< dp: day: 0 [0, -5] day: 1 [0, -2] day: 2 [2, -2] day: 3 [0, 0] day: 4 [0, 0] day: 5 [0, 0] maxProfit0 <<< dp: day: 0 [0, -5] day: 1 [0, -2] day: 2 [2, -2] day: 3 [4, -2] day: 4 [0, 0] day: 5 [0, 0] maxProfit0 <<< dp: day: 0 [0, -5] day: 1 [0, -2] day: 2 [2, -2] day: 3 [4, -2] day: 4 [4, 1] day: 5 [0, 0] maxProfit0 <<< dp: day: 0 [0, -5] day: 1 [0, -2] day: 2 [2, -2] day: 3 [4, -2] day: 4 [4, 1] day: 5 [4, 1] main <<< output: 4 maxProfit <<< day: 1 cost: -2 profit: -3 maxProfit: 0 maxProfit <<< day: 2 cost: -2 profit: 2 maxProfit: 0 maxProfit <<< day: 3 cost: -2 profit: 4 maxProfit: 2 maxProfit <<< day: 4 cost: 1 profit: -1 maxProfit: 4 maxProfit <<< day: 5 cost: 1 profit: 4 maxProfit: 4 main <<< output: 4 2,5 main <<< prices: [2, 5] main <<< output: 3 maxProfit <<< day: 1 cost: -2 profit: 3 maxProfit: 0 main <<< output: 3
We are provided an input line with the prices for the stock. Our test code seems to read the input line, allocate and populate an int[] array, display the contents of the array, and then call two implementations of the function of interest.
During execution both functions seem to display additional information which should help us follow the logic of the implementations. Both solutions were accepted by LeetCode.
I want to emphasize that the code for both solutions was edited multiple times. It is hard to show the progression from an empty function to the final version.
/**
* 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[] of prices ****
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 result ****
System.out.println("main <<< output: " + maxProfit0(prices));
// **** call function of interest and display result ****
System.out.println("main <<< output: " + maxProfit(prices));
}
This is the test scaffold which IS NOT PART OF THE SOLUTION.
It seems to follow the description we have for the test cases. At this time there is not much to add.
/**
* Find the maximum profit you can achieve.
* Building dp[][] array.
*
* 210 / 210 test cases passed.
* Status: Accepted
* Runtime: 3 ms
* Memory Usage: 39.2 MB
*/
static public int maxProfit0(int[] prices) {
// **** initialization ****
int len = prices.length;
// **** sanity check(s) ****
if (len <= 1) return 0;
if (len == 2 && prices[1] > prices[0])
return prices[1] - prices[0];
else if (len == 2 && prices[0] > prices[1])
return 0;
// **** initialize dp[] ****
int[][] dp = new int[len][2];
dp[0][0] = 0;
dp[0][1] = -prices[0];
dp[1][0] = Math.max(dp[0][0], dp[0][1] + prices[1]);
dp[1][1] = Math.max(dp[0][1], dp[0][0] - prices[1]);
// **** loop through the remaining days ****
for (int day = 2; day < len; day++) {
// **** have no stock ****
dp[day][0] = Math.max(dp[day - 1][0], dp[day - 1][1] + prices[day]);
// **** have stock ***
dp[day][1] = Math.max(dp[day - 1][1], dp[day - 2][0] - prices[day]);
// ???? ????
System.out.println("maxProfit0 <<< dp:");
for (int i = 0; i < len; i++)
System.out.println("day: " + i + " " + Arrays.toString(dp[i]));
}
// ***** return max profit (not holding a stock) ****
return dp[len - 1][0];
}
In this case I followed the steps in the article and eventually I ended with a two dimensional array of values. The dp[][] array holds the values per day and the information if we sold or not stock.
We initialize the `len` variable since we will need the length of the array a few times.
We then perform a sanity checks. On earlier passes I was going with using a recursive call, but at some point changed route and went with an iterative approach.
We initialize the first two entries in the dp[] array. This is done due to the 1-day cooldown.
At this point we are ready to traverse the rest of the entries in the prices array and populate the rest of the dp[] array. As is typical with the approach of using a table, we will find the answer for the problem in the last entry: dp[len – 1][0].
In the loop we need to populate the two conditions. In one we have no stock and in the second we have a stock. We use the Math.max() function since each condition has two sub conditions.
After the loop ends we have populated the dp[] table and our answer is in the specified last entry. The reason we pick dp[len – 1][0] is that this is the last entry and we do not have a stock in our hands for which we would have spent money buying it without the opportunity of being able to sell the stock on the last day.
/**
* Find the maximum profit you can achieve.
*
* 210 / 210 test cases passed.
* Status: Accepted
* Runtime: 2 ms
* Memory Usage: 39 MB
*
* After replacing Math.max():
*
* 210 / 210 test cases passed.
* Status: Accepted
* Runtime: 0 ms
* Memory Usage: 36.5 MB
*/
static public int maxProfit(int[] prices) {
// **** sanity check(s) ****
if (prices.length <= 1) return 0;
// **** initialization (states) ****
int maxProfit = 0;
int cost = -prices[0];
int profit = 0;
// **** traverse the prices array ****
for (int day = 1; day < prices.length; day++) {
// **** save max profit ****
int tmp = maxProfit;
// **** update max profit ****
// maxProfit = Math.max(maxProfit, profit);
maxProfit = maxProfit > profit ? maxProfit: profit;
// **** compute profit ****
profit = cost + prices[day];
// **** update cost ****
// cost = Math.max(cost, tmp - prices[day]);
cost = cost > tmp - prices[day] ? cost : tmp - prices[day];
// ??? ?????
System.out.println( "maxProfit <<< day: " + day + " cost: " + cost +
" profit: " + profit + " maxProfit: " + maxProfit);
}
// **** return the max of these values ****
//return Math.max(maxProfit, profit);
return maxProfit > profit ? maxProfit : profit;
}
This code implements a similar approach but does not make use of building the dp[] table. That saves space as is illustrated in the comments section of the function.
By replacing the Math.max() function with an on-line check, we achieved better execution time. In retrospect I should have done the same to the implementation of the first function. At this time I will leave it as optional points. That said; if you check the timing on that implementation, I will update this post with your results.
As the days in the week go by (today is Thursday), it seems that I tend to get tired earlier in the day. In general I tried to solve problems first thing in the day. In the afternoon towards the end of the day I tend to do documentation, read and watch videos for research.
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