Problem Description:

Given an array X, the span S[i] of X[i] is the maximum number of consecutive elements X[j] immediately preceding X[i] and such that X[j] <= X[i]

What you need to do:

Develop a C++ function that has an array of double numbers and the size of the array as its parameters, and then fill an integer array of the same size the span of each element in the first array.

The prototype of the function is shown below:

  void calculateSpan(double X[], int size, int S[]);
  

First develop the function using a quadratic algorithm. (This should be easy).

  void calculateSpan(double X[], int size, int S[])
  {
      for (i = 0; i < size; i++) {
          S[i] = 1;
          for(j = i - 1; j >= 0 && X[i] > X[j]; j = j - 1)
              S[i] ++;
      }
  }

Then develop a linear algorithm to solve the problem using a Stack. Try to analyze why this algorithm is a linear one.

  void calculateSpan(double X[], int size, int S[])
  {
      create an empty stack, IS, to store indices;
      for (i = 0; i < size; i++) {
          while ( !IS.isempty() && X[i] > X[IS.top()] )
              IS.pop();

          if (IS.isempty())
              S[i] = i + 1;
          else
              S[i] = i - IS.top();

          IS.push(i);
      }
  }

Every index would be pushed into the stack once, and popped out of the stack at most once.