Site icon Study Algorithms

Finding spans in an array.

Question: Find spans in an array. Given an array arr[], the SPAN s[i] of arr[i] is the maximum number of consecutive elements arr[j] immediately before arr[i] such that arr[j] <= arr[i].

Let us try to understand the question once again. This is a very common problem in stock markets to find the peaks. Spans have applications to financial analysis(Example:- You might have heard a saying “STOCKS AT 52 WEEK HIGH”). The span of a stocks price on certain day, i , is the maximum number of consecutive days (up-to the current day) the price of the stock has been less than or equal to its price on i. As an example let us consider the following diagram:-

Day : Index i Input Array arr[i] S[i] : Span of arr[i]
0 6 1
1 3 1
2 4 2
3 5 3
4 2 1

Now let us try to find an algorithm to find the spans.

The simplest method would be to find the contiguous days with less stock price for each day.

#include<stdio.h>

int main(void)
{
	int arr[10];

	/*
	input an array of integers
	*/
	int i,j;
	for(i=0;i<10;i++)
		scanf("%d",&arr[i]);

	//to store the spans
	int new_arr[10];

	for(i=0;i<10;i++)
	{
		j = i-1;
		int count = 0;
		//counting the contagious smaller elements
		while(arr[j] <= arr[i] && j>=0)
		{
			count++;
			j--;
		}
		new_arr[i] = count;
	}

	printf("The spans are:- ");
	for(i=0;i<10;i++)
		printf("%d ",new_arr[i]);

	return 0;
}
Exit mobile version