Best Time to Buy and Sell Stock II (with Explanation)

Hello, everyone.
Today I want to share my thinking process to understand solution from leetcode problem Best Time to Buy and Sell Stock II. I hope this post can help anyone like me who need more explanation how to turn it into code and why the code solution is like that. Please read the leetcode page first.

For example, assume we have black dots represents stock prices and a pointer walking around the dots. Initial state of the pointer is 0.

We know that the pointer is walking around, and sometimes it's reach lower value and higher value for specific interval, we see peaks and valleys, right?

If we analyze the graph, we notice that the points of interest are the consecutive valleys and peaks.

Mathematically speaking: 

The key point is we need to consider every peak immediately following a valley to maximize the profit. In case we skip one of the peaks (trying to obtain more profit), we will end up losing the profit over one of the transactions leading to an overall lesser profit.

For example, in the above case, if we skip peak_i and valley_j trying to obtain more profit by considering points with more difference in heights, the net profit obtained will always be lesser than the one obtained by including them, since C will always be lesser than A+B.

But how do we detect whether it's a valley, a peak, or just an ordinary dots (like other black dots)? Lets see on this picture below.

Try by yourself, run the pointer through all black dots. Feel that every time your pointer on the black dots, you can analyze that "is this current dot a peak or valley?", can't you?

We have two option, whether check the dot before, or the dot after?

Let's analyze, if we choose the dot before as our benchmark and our pointer is on that position, see picture below.

Do you have any idea what the criteria is? When the pointer is in minus gradient, we only know the dots before is always greater than current dots, also the valley. The opposite is, when the pointer with positive gradient, we only know the dots before is smaller than the current dots, also the peak. But if we choose it as criteria to check current dots, the result is all dots is detected as peak and valley. So, we can't use the dot before as criteria when to current pointer.

Lets, check another option, the dots after.

Because when first time we see dot after is more than current value, we know that current value is a valley. And when first time we see dot after is less than current value, we know that current value is a peak.

From this problem, I learn to solve this problem, we need to know:

1. What is the pointer role as? The criteria is different when the pointer is not the thing that we expect to be peak or valley. I should have clear assumption about the pointer. Often I feel difficult to decide whether it's need to be less than, greater than, less than equals, or anything else. The different assumption of the pointer role. The different criteria I need to use.
2. I need to know what I want to see. From the problem, what is goals that I need to reach. So, how I have to reach that goal with my assumption?

But for the 3rd Solution, we know something so easy. Why?

as you can see, we don't don't care with the negative gradient.