The Stock Span Problem is a classic problem in computer science that involves finding the number of days that a given stock's price is higher than or equal to the price on a given day. This problem can be solved using a variety of algorithms, but one of the most popular and efficient ways to solve it is through the use of a stack data structure in C++.
The problem can be defined as follows: given a list of stock prices for N days, find the number of days that the stock price is higher than or equal to the price on a given day. This is known as the "span" of the stock price. For example, if the stock prices for the first five days are [100, 80, 60, 70, 60], then the span of the stock price on the first day would be 1, since the price on the first day is higher than or equal to the price on the first day. The span of the stock price on the second day would be 2, since the price on the second day is lower than the price on the first day, but is still higher than or equal to the price on the second day.
One way to solve this problem is to use a stack data structure. A stack is a last-in, first-out (LIFO) data structure that allows for easy insertion and removal of elements. In this case, we will use a stack to keep track of the stock prices and the corresponding spans.
To begin, we will create a stack and push the first stock price and its corresponding span (1) onto the stack. We will then iterate through the rest of the stock prices, starting with the second day. For each day, we will compare the current stock price to the top of the stack. If the current stock price is greater than or equal to the top of the stack, we will pop the top of the stack and add the span to the current span. We will then push the current stock price and its corresponding span onto the stack. If the current stock price is less than the top of the stack, we will push the current stock price and its corresponding span (1) onto the stack.
The following is an example of the stack algorithm in C++:
#include <iostream> #include <stack> using namespace std; int main() { // Stock prices for 7 days int prices[7] = {100, 80, 60, 70, 60, 75, 85};
int n = sizeof(prices)/sizeof(prices[0]); // Create stack and push first stock price and span (1) stack<int> st; st.push(0); // Output array to store spans int s[n]; // First stock span is always 1 s[0] = 1; // Iterate through rest of stock prices for (int i = 1; i < n; i++) { // Pop elements from stack while stack is not empty and top of stack
// is less than or equal to price[i] while (!st.empty() && prices[st.top()] <= prices[i]) { st.pop(); } // If stack becomes empty, then price[i] is greater than all elements
// on left of it, i.e. price[0], price[1],..price[i-1] s[i] = (st.empty()) ? (i + 1) : (i - st.top()); // Push this element to stack st.push(i); }
// Print spans for (int i = 0; i < n; i++) { cout << "Span for day " << i+1 << ": " << s[i] << endl; } return 0; }
This code will output the span for each day in the stock prices array, such as:
Span for day 1: 1 Span for day 2: 2 Span for day 3: 1 Span for day 4: 3 Span for day 5: 1 Span for day 6: 2 Span for day 7: 4
This algorithm has a time complexity of O(n) because it iterates through the stock prices array once and performs a constant number of operations on the stack for each day. This makes it an efficient solution for solving the Stock Span Problem. Additionally, this algorithm can be easily modified to handle more complex stock data, such as incorporating the date and time of each stock price and calculating the span based on specific time intervals.
In conclusion, the Stock Span Problem is a classic problem in computer science that can be efficiently solved using a stack data structure in C++. By using a stack to keep track of stock prices and corresponding spans, this algorithm can quickly and accurately calculate the span for each day in a given stock prices array. This algorithm can be easily modified to handle more complex stock data and is a useful tool for financial analysis and prediction.
