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?

CodePudding user response：

I can’t make heads or tails of that solution either. It might be bucket sorting.

“Monotonic queue” is new to me, but it is the right trick here. Despite the framing in terms of subsequences, the order of the input doesn’t matter, so we can go ahead and sort it, which makes the longest valid subsequence contiguous because the interior elements make the subsequence longer without affecting the min or max.

The function mapping each right endpoint to the best corresponding left endpoint is monotone. Hence we can write the usual two nested loops where the inner one amortizes. (This is ignoring the “no smaller than m” criterion, which we can handle by filtering the candidate intervals.)

#include <algorithm>
#include <cassert>
#include <iostream>
#include <optional>
#include <vector>

int main() {
  int n, m, k;
  while (std::cin >> n >> m >> k) {
    assert(n >= 0);
    assert(k >= 0);
    std::vector<int> a(n);
    for (int i = 0; i < n;   i) {
      std::cin >> a[i];
    }
    std::sort(a.begin(), a.end());
    std::optional<int> longest;
    int l = 0;
    for (int r = 0; r < n;   r) {
      while (a[r] - a[l] > k) {
          l;
      }
      if (a[r] - a[l] >= m) {
        longest = std::max<std::optional<int>>(longest, r - l   1);
      }
    }
    assert(longest);
    std::cout << *longest << "\n";
  }
}

CodePudding user response：

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
        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 between pos and the current position
            // 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[l1]] is the minimum element between pos and the current position
            // 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;
}