fork download 
  1. //
  2. //  main.cpp
  3. //  Stock Span
  4. //
  5. //  Created by Himanshu on 11/09/21.
  6. //
  7.  
  8. #include <iostream>
  9. #include <stack>
  10. using namespace std;
  11.  
  12.  
  13.  
  14. void printArray (int arr[], int n) {
  15.     for (int i=0; i<n; i++) {
  16.         cout<<arr[i]<<" ";
  17.     }
  18.     cout<<endl;
  19. }
  20.  
  21. void solve(int S[], int arr[], int n) {
  22.     stack<int> st;
  23.  
  24.     S[0] = 1;
  25.     st.push(0);
  26.  
  27.     for (int i=1; i<n; i++) {
  28.  
  29.         while (!st.empty() && arr[st.top()] < arr[i]) {
  30.             st.pop();
  31.         }
  32.  
  33.         if (st.empty()) {
  34.             S[i] = i + 1;
  35.         } else {
  36.             S[i] = i - st.top();
  37.         }
  38.  
  39.         st.push(i);
  40.     }
  41. }
  42.  
  43. int main () {
  44.     int n = 7;
  45.     int arr[] = {100, 80, 60, 70, 60, 75, 85};
  46.     int S[n];
  47.  
  48.     cout<<"Initail array:"<<endl;
  49.     printArray(arr, n);
  50.  
  51.     solve (S, arr, n);
  52.  
  53.     cout<<"Stock Span:"<<endl;
  54.     printArray(S, n);
  55.  
  56.     return 0;
  57. }
  58.  
Success #stdin #stdout 0s 5544KB
comments (?)
stdin 
Standard input is empty
stdout 
Initail array:
100 80 60 70 60 75 85 
Stock Span:
1 1 1 2 1 4 6
https://ideone.com/YsWUc0
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!