*808*

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; }