An Algorithm Problem About Monotonic Queue

Question

Here is the description of the problem:

There is a sequence of integers. Your task is to find the longest subsequence that satisfies the following condition: the difference between the maximum element and the minimum element of the subsequence is no smaller than m and no larger than k.

I have searched on the Internet and got a solution like this:

#include<iostream>
using namespace std;
#define maxn 100010
int n,m,k,q_max[maxn],q_min[maxn],a[maxn];
int main()
{
    while(cin>>n>>m>>k)
    {
        for(int i=1;i<=n;i++)
          cin>>a[i];
        int l1=0,r1=0,l2=0,r2=0,ans=0,pos=0;
        for(int i=1;i<=n;i++)
        {
            while(r1>l1&&a[q_max[r1-1]]<=a[i])         
              r1--;            
            q_max[r1++]=i;
            while(r2>l2&&a[q_min[r2-1]]>=a[i])       
              r2--;                    
            q_min[r2++]=i;
            while(r1>l1&&r2>l2&&a[q_max[l1]]-a[q_min[l2]]>k)    
            {
                if(q_max[l1]<q_min[l2])
                  pos=q_max[l1++];
                else
                  pos=q_min[l2++];
            }
            if(r1>l1&&r2>l2&&a[q_max[l1]]-a[q_min[l2]]>=m)    
              ans=max(ans,i-pos);
        }   
        cout<<ans<<endl;
    }
    return 0;
} 

I have understood the way a typical Monotonic Queue works, but I can't understand why the specific usage of it in this question can be correct. Could you explain it?

Answer 1

The algorithm you posted finds the longest contiguous subarray with difference between min and max elements >= m and <= k.

Here it is with comments:

#include<iostream>
using namespace std;
#define maxn 100010
int n,m,k,q_max[maxn],q_min[maxn],a[maxn];
int main()
{
    // This loop processes multiple test cases.  get n,m,k for next one
    while(cin>>n>>m>>k)
    {
        // input sequence
        // note that it strangely starts at a[1] instead of a[0], for
        // no good reason
        for(int i=1;i<=n;i++)
          cin>>a[i];
        
        int l1=0,r1=0,l2=0,r2=0,ans=0,pos=0;
        for(int i=1;i<=n;i++)
        {
            // we maintain a monotonic queue in q_max between l1 and r1
            // a[q_max[l1]] is the maximum element with index > pos and <= i
            // here we add i to the end
            while(r1>l1&&a[q_max[r1-1]]<=a[i])         
              r1--;            
            q_max[r1++]=i;

            // we also maintain a monotonic queue in q_min between l2 and r2
            // a[q_mmin[l2]] is the minimum element with index > pos and <= i
            // here we add i to the end
            while(r2>l2&&a[q_min[r2-1]]>=a[i])       
              r2--;                    
            q_min[r2++]=i;

            // while max-min > k, we need to increase pos, removing
            // elements from the queues.  This will reduce max and/or
            // increase min
            while(r1>l1&&r2>l2&&a[q_max[l1]]-a[q_min[l2]]>k)    
            {
                // increase pos by removing the earliest element
                // in either queue.  Note that they cannot be the same
                // the corresponding values differ by more than k
                if(q_max[l1]<q_min[l2])
                  pos=q_max[l1++];
                else
                  pos=q_min[l2++];
            }

            // If the max-min difference is big enough, then the current
            // sequence is valid.  Remember it if it's the longest so far
            if(r1>l1&&r2>l2&&a[q_max[l1]]-a[q_min[l2]]>=m)    
              ans=max(ans,i-pos);
        }   
        cout<<ans<<endl;
    }
    return 0;
}