The Stock Span Problem

Suppose, for a stock, we have a series of n daily price quotes, the span of the stock's price on a given day is defined as the maximum number of consecutive days just before the given day, for which the price of the stock on the current day is less than or equal to its price on the given day.

Let, Price (i) = price of the stock on day "i".

Then, Span (i) = max {k : k >= 0 and Price (j) <= Price (i) for j = i - k, .., i}

Thus, if Price (i-1) > Price (i), then Span (i) = 0.

Reference: http://en.wikipedia.org/wiki/Stack_%28abstract_data_type%29#The_Stock_Span_Problem

Time Complexity: O(n)
Space Complexity: O(n) for stack.