[Light OJ] 1093 - Ghajini

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 1093 - Ghajini
Source            : Light Online Judge
Category          : Data Structure
Algorithm         : Sliding Window
Verdict           : Accepted

#include "bits/stdc++.h"
 
using namespace std;
 
const int maxn = 1e5 + 5;
 
int arr[maxn];
int N, D;
 
inline int maxDiference()
{
    int maxDif = 0;
    deque <int> dqMin, dqMax;
    for (int i=0; i<N; i++)
    {
        int num = arr[i];
        while (!dqMin.empty() and dqMin.front()>num) dqMin.pop_front();
        dqMin.push_front(num);
        if (i >= D and arr[i-D] == dqMin.back()) dqMin.pop_back();
 
        while (!dqMax.empty() and dqMax.front() < num) dqMax.pop_front();
        dqMax.push_front(num);
        if (i >= D and arr[i-D] == dqMax.back()) dqMax.pop_back();
 
        if (i >= D-1)
        {
            int mini = dqMin.back();
            int maxi = dqMax.back();
            maxDif = max(maxi-mini, maxDif);
        }
    }
    return maxDif;
}
 
 
int main()
{
    int tc;
    scanf("%d", &tc);
    for (int tcase = 1; tcase <= tc; tcase++)
    {
        scanf("%d %d", &N, &D);
        for (int i = 0; i < N; i++) scanf("%d", &arr[i]);
        printf("Case %d: %d\n", tcase, maxDiference());
    }
}