單調列隊

11078_dq.cpp

#include <bits/stdc++.h>
using namespace std;

int t, n, maxv;
deque<int> dq;
int main(int argc, char *argv[])
{
    cin >> t;
    while(t-- && cin >> n)
    {
        maxv = INT_MIN;
        dq.clear();
        
        for(int i = 0, in; i < n && cin >> in; i++)
        {
            if(!dq.empty()) maxv = max(maxv, dq.front()-in);
            
            while(!dq.empty() && dq.back() <= in)
                dq.pop_back();
                
            dq.push_back(in);
        }
        cout << maxv << '\n';
    }
}