## Stock span
Given a list of rates of a certain stock for some number of days, the **stock span**​ is the number of consecutive days (before a specific day) when the price of the stock was less than or equal to the price on this specific day.

### Implementation
Create a stack and an empty list of stock spans.

Traverse through the list of stock rates:
  - For the first day, the stock-span is $1$ by default.
  -  When you've calculated the stock span for a certain day, add this to the corresponding index in the list of stock spans. Push the index of this element onto the stack.
  - To calculate the stock span for a certain day:
    - Check the stock price that corresponds to the index on top of the stack. 
    - Compare it with the stock price at the current day. If it's smaller than the price on the current day, pop this index out of the stack. Repeat the same process with the new stack top. 
    - When the stock price that corresponds to the index at the top of​ the stack​ is greater than the stock price of the current day, calculate the stock-span by subtracting the index at the top of the stack from the index of the current day.



#include <iostream>
#include <stack>
using namespace std;

void span(int rates[], int days, int stockspan[]){

  stack<int> stack; //Creating an empty stack

  //Base case
  stockspan[0] = 1;
  stack.push(0);

  for(int i=1; i<days; i++) //iterating through the rates
  {
    //Pop elements out of stack until either: 1) The stack gets empty
    //or 2) the rate at stack top turns out to be larger than the rate
    //at the current element
    while(rates[i] > rates[stack.top()])
    {
      stack.pop();

      if(stack.empty()) 
      {
        break;
      }
    }

    //set the stockspan values.
    if(!stack.empty())
    {
      stockspan[i] = i - stack.top();
    }
    else
    {
      stockspan[i] = i+1;
    }

    stack.push(i);

  }
}
int main() {

  int size = 6;
  int rates[size] = {31,27,14,21,30,22};
  int stockspan[size];

  span(rates, size, stockspan);

  for(int i=0; i<size; i++)
  {
    cout<< stockspan[i] << ", ";
  }
  
}

def span(rates):
    
    stockspan = []
    stack = [] # Creating an empty stack

    # Base case
    stockspan.append(1)
    stack.append(0)
    for i in range(1, len(rates)):

      # Pop elements out of stack until either: 1) The stack gets empty
      #or 2) the rate at stack top turns out to be larger than the rate
      #at the current element
      while rates[i] > rates[stack[-1]]:
        stack.pop()

        if len(stack) is 0:
          break
      
      # Set the stockspan values.
      if len(stack) > 0:
          stockspan.append(i - stack[-1])
      else:
          stockspan.append(i + 1) 

      stack.append(i)
    
    return stockspan



rates = [31, 27, 14, 21, 30, 22]
stockspan = span(rates)
print(stockspan)

The stock span problem in C++ and Python

Stock span

Implementation

Example code