Once upon a time, there was a stock trader named John. John was always looking for new ways to improve his trading strategies and make more profits. One day, he came across a problem while analyzing the stock market data.
John had a list of daily stock prices for a particular stock, and he wanted to calculate the "stock span" for each day. The stock span for a particular day is defined as the maximum number of consecutive days (including the current day) before the current day, such that the price of the stock on all those days is less than or equal to the price on the current day.
For example, if the stock prices for the last 7 days were {100, 80, 60, 70, 60, 75, 85}, then the span values for the corresponding 7 days are {1, 1, 1, 2, 1, 4, 6}.
John wanted to automate this calculation process so that he could quickly analyze the stock market data and make better trading decisions. However, he was not sure how to write an efficient algorithm for this problem.
Can you help John by writing an algorithm to calculate the stock span for each day in the given list of stock prices?
Input Format
The first line contains an integer N where N is the number of days and in the next line, you have to take an integer array name prices which contains N prices.
Sample Input:
N = 7
price[] = [100 80 60 70 60 75 85]
Output:
1 1 1 2 1 4 6
Traversing the given input span for 100will be 1, 80 is smaller than 100 so thespan is 1, 60 is smaller than 80 so thespan is 1, 70 is greater than 60 so thespan is 2 and so on. Hence the output willbe 1 1 1 2 1 4 6.