[Leetcode Solution] Best Time to Buy and Sell Stock i & ii & II

Analysis

• Best Time I
• The max profit can get from selling stock at i-th day is buying the stock at day at which the stock is the cheapest during 1-th day to i-th day
• One pass use to variables. First variable min record the minimum price from the first day to now. Second variable max record the max profit can get 
• Best Time II
• Along with the days passing, if the price is rising, then but at the first day and sell at the last day
• One pass with two pointers, pointer p points the start day. The pointer q points the next day. If the price is continuous rising, move q backward until price drops. Then this is one deal which buy at p and sell at q. Then p points to q+1 and iteratively do the same thing
• Best Time III
• Almost the same as Best Time I. We use a pointer to scan the prices in time ascending order to get the max profit can get in the first k days denotes as f[k]. And use another pointer to scan the prices in time descending order to get the max profit can get in the last p days denotes as g[p]. 
• Then the total max profit can get is the max(f[p]+g[size-p]

Note

Code