Stock_Span_Problem.cpp

// C++ program for a linear time solution for stock
// span problem without using stack
#include <iostream>
#include <stack>
using namespace std;

// An efficient method to calculate stock span values
// implementing the same idea without using stack
void calculateSpan(int A[], int n, int ans[])
{
	// Span value of first element is always 1
	ans[0] = 1;

	// Calculate span values for rest of the elements
	for (int i = 1; i < n; i++) {
		int counter = 1;
		while ((i - counter) >= 0 && A[i] >= A[i - counter]) {
			counter += ans[i - counter];
		}
		ans[i] = counter;
	}
}

// A utility function to print elements of array
void printArray(int arr[], int n)
{
	for (int i = 0; i < n; i++)
		cout << arr[i] << " ";
}

// Driver program to test above function
int main()
{
	int price[] = { 10, 4, 5, 90, 120, 80 };
	int n = sizeof(price) / sizeof(price[0]);
	int S[n];

	// Fill the span values in array S[]
	calculateSpan(price, n, S);

	// print the calculated span values
	printArray(S, n);

	return 0;
}