We are given a list of prices of a stock for N number of days. We need to find stock span for each day. Span is defined as number of consecutive days before the given day where the price of stock was less than or equal to price at given day. For example, {100, 60,70,65, 80, 85} span for each day will be {1, 1, 2, 1, 4, 5}.
For first day span is always 1. In example, notice that on day 2, price of stock is 60 and there is no day prior to it where price was less than 60. Hence span for day 2 is 1 again. For day 3, price at day 2 (60) is less than 70, hence span for day 3 is 2. Similarly, for day 4 and day 5. Remember days should be consecutive, that why span for day 4 is 1 even though there was a day 2 where price was less than 65.
From above implementation, notice that the day of real interested to us is the day where price was last seen greater than current day price. So we need to check last price which was greater than price today. So maintain a stack which contains prices seen in decreasing order.
So while scanning prices on given days, check if there are prices which are less than current price. If yes, just pop them out. When you encounter a price which is greater than current price, stock span with maximum profit of current day is difference between day of that price and current day. So looking carefully, it becomes apparent that, storing index of last greatest seen price would make things easier as compared to storing actual price. Hence day is store i on stack, price[i] will give us the price of stock on day i.
Algorithm to detect stock span
- Initialize span of day 1 as 1.
- Put day 1 on to stack.
- For all days starting from day 2, repeat following steps.
- If price of stock on day at top of stack is less than price of stock on current day, Pop the index from stack.
- If price of stock on the day on top of stack is greater than price of stock on current day, calculate span as current day – day at top of stack.
- Push current day index on to stack.