Join the social network of Tech Nerds, increase skill rank, get work, manage projects...
 
  • find the longest sub-arraythat all of its elements are less or equalA[i]

    • 0
    • 0
    • 0
    • 1
    • 0
    • 0
    • 0
    • 239
    Answer it

    I have an array A[1,...,n] of positive numbers, for example:

    [1, 2, 5, 3, 7, 2, 8, 4]
    

    I need to build an array S[1,...,n] according to the definition:

    S[i] = max {k|ik <ji :A[j]  A[i] and k  i}
    

    It means to find the longest sub-array A[i − k,..,i] that all of its elements are less or equal A[i] for each index in the array.

    I need to write an algorithm that creates the array S in O(n) using Stack.

    For example for the array [1,2,4,3,5] i need to return the array [1,2,3,2,5]

    Thank you.

 1 Answer(s)

  • Hi rotemhas,

        Following C++ code will solve your problem.

    #include <iostream>
    #include <stack>
    
    using namespace std;
    
    void calculate(int arr[], int n)
    {
            // Create a stack and push index of first element to it
            stack<int> st;
            st.push(0);
    
            // maximum range value of first element is always 1
            int max = 1;
            int tmp = 0;
            int index = 0;
    
            // Calculate range values for rest of the elements
            for ( int i = 1; i < n; i++) {
                    // Pop elements from stack while stack is not empty and top of
                    // stack is smaller than price[i]
                    while (!st.empty() && arr[st.top()] < arr[i])
                            st.pop();
    
                    // If stack becomes empty, then arr[i] is greater than all elements
                    // on left of it, i.e., arr[0], arr[1],..arr[i-1].  Else arr[i]
                    // is greater than elements after top of stack
                    tmp = (st.empty())?(i+1):(i-st.top());
    
                    if(tmp > max) {  // to maintain a record for longest range upto i-th element
                            max = tmp;
                            index = i;
                    }
    
                    // Push this element to stack
                    st.push(i);
            }
            int startIndex = index-max+1; // startIndex will point to the starting index of subarray
            int limitIndex = index;       // limitIndex will point to last index of sub array according to the problem.
    
            //to print the range
            cout << "The final subarray will be  : ";
            for ( int i = startIndex; i <= limitIndex; i++)
                    cout << arr[i] << " ";
            cout << endl;
    
            return;
    }
    
    int main()
    {
            int n;
            cout << "Enter the size of array : ";
            cin >> n;
            int arr[n];
            cout << "Enter the elements of array : ";
            for ( int i = 0; i < n; i++)
                    cin >> arr[i];
    
            calculate(arr,n);
    
            return 0;
    }
    

    Sample Inputs and Outputs

    Enter the size of array : 7
    Enter the elements of array : 100 80 60 70 60 75 85
    The final subarray will be  : 80 60 70 60 75 85 
    
    Enter the size of array : 6
    Enter the elements of array : 1 1 1 1 1 1  
    The final subarray will be  : 1 
    
    Enter the size of array : 5
    Enter the elements of array : 1 2 3 4 5
    The final subarray will be  : 1 2 3 4 5
    
    Enter the size of array : 8
    Enter the elements of array : 1 2 5 3 7 2 8 4
    The final subarray will be  : 1 2 5 3 7 2 8
    

    Thanks for posting your problem on Findnerd :)

Sign In
                           OR                           
                           OR                           
Register

Sign up using

                           OR                           
Forgot Password
Fill out the form below and instructions to reset your password will be emailed to you:
Reset Password
Fill out the form below and reset your password: