Leetcode 123: Buy and sell stock III

June 8, 2017

Problem statement

It is hard level algorithm. And it can be solved using dynamic programming. It is challenging task to solve a dynamic programming algorithm.

Now it is 10:39 pm, Julia likes to choose a topic to do a short research, what you should do if the algorithm is too hard to solve? 30 minutes research.

10 steps to master dynamic programming

1. Watch a video to relax, I found one - google developer talked about competitive programming. Here is the link, 1 hour 44 minutes.

2. Read a math lecture note from brown university, lecture note is here. Read a mathematician web page and learn some research idea here.

3. Dynamic programming should be renamed. Discussion is here.

4. Read a median age article and talk about AWS - link is here.

5. Work on interviewbit.com dynamic programming problems, the link is here. (June 16, 2017)

Follow up 

June 9, 2017

Julia's C# practice is here.

June 12, 2017

Julia's talk about the algorithm design

It is a good ritual to talk about the design, make a story, structure the story the way easy to recall, and also very well structured highlighted with keywords using different colors. The true nature of dynamic programming reminds us spend more time to write a story, spend less time to write the code.

Here are the highlights of story to buy and sell stocks. One transaction, multiple choice of purchase time, how to find maximum value? how to introduce the recurrence formula?

First let us talk about buy and sell stocks algorithm here on Leetcode 123. As a recursive solution nature, we only need to discuss one transaction in the design. We need to consider when to purchase, when to sell.

One transaction leads us to think about the last transaction. The last time stamp index to sell or not sell the stock.

Assume that we sell at time stamp index, and we can purchase anytime before index, in other words, any j from 0 to index – 1. The overall profit can be expressed using  the profit based on j and then last transaction profit prices[index] – prices[j].

Let us talk about multiple choices, and what is the optimal value? Find the maximum values in all the options.

Next, let us introduce the recurrence formula. Define a profit function called profit(k, j), where k is the number of transactions and j is the time stamp. 


f[k, index] = max(f[k, index - 1], max(prices[index] - prices[j] + f[k - 1, j]) for any j in range of [0, index - 1])

Follow up 

I had a mock interview on January 28, 2018, and after the mock interview the peer shared with me how he learned the algorithm through $50.00 purchase of courses on algoexpert.io. I found this free lecture on the algorithm Leetcode 123: Buy and Sell stock III.