Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define N 300300
using namespace std;

int n,k,re=1,a[N],f[N],g[N],Min[N],Max[N],posMin[N],posMax[N];
int lMin,rMin,lMax,rMax,newposMin[N],newposMax[N];

void updateMin(int val,int pos)
{
    if (val>Min[rMin])
    {
        Min[++rMin]=val; posMin[rMin]=newposMin[rMax]=pos;
        return;
    }
    while (rMin>=lMin && val<=Min[rMin]) rMin--;
    if (rMin<lMin || val>Min[rMin])
    {
        Min[++rMin]=val; newposMin[rMin]=pos; 
    }
}

void updateMax(int val,int pos)
{
    if (val<Max[rMax])
    {
        Max[++rMax]=val; posMax[rMax]=newposMax[rMax]=pos;
        return;
    }
    while (rMax>=lMax && val>=Max[rMax]) rMax--;
    if (rMax<lMax || val<Max[rMax])
    {
        Max[++rMax]=val; newposMax[rMax]=pos;
    }
}

void calc(int f[])
{
    memset(Min,0,sizeof(Min));
    memset(posMin,0,sizeof(posMin));
    memset(Max,0,sizeof(Max));
    memset(posMax,0,sizeof(posMax));
    Min[lMin=rMin=1]=a[0]; posMin[1]=newposMin[1]=0;
    Max[lMax=rMax=1]=a[0]; posMax[1]=newposMax[1]=0;
    f[0]=0;
    for (int i=1;i<n;i++)
    {
        updateMin(a[i],i);
        updateMax(a[i],i);
        int ok=1;
        while (Max[lMax]-Min[lMin]>k)
        {
            ok=0;
            if (newposMax[lMax]<newposMin[lMin]) lMax++;
            else lMin++;
        }
      f[i]=max(posMax[lMax],posMin[lMin]);
    }
    for (int i=0;i<n;i++) f[i]=max(i-f[i]+1,(i?f[i-1]:0));
}

int main()
{
    cin >> n >> k;
    for (int i=0;i<n;i++) scanf("%d",&a[i]);
    calc(f);
    reverse(a,a+n);
    calc(g);
    reverse(g,g+n);
    for (int i=0;i<n-1;i++) re=max(re,f[i]+g[i+1]);
    cout << re << endl;
    return 0;
}

Code mẫu của ladpro98

#include <iostream>
#include <deque>
#include <stdio.h>
#include <cstdio>

using namespace std;

const   long maxN = 300005;

struct e {
    long x,p;
};

deque<e> ma,mi;
long a[maxN];
long rleft[maxN];
long rright[maxN];
long mleft[maxN];
long mright[maxN];
long n,k;


void init() {

    scanf("%ld %ld", &n, &k);
    for(long i=1; i<=n; i++) {
        scanf("%ld", &a[i]);
    }
}

e rec(long a, long b) {
    e t;
    t.p = b;
    t.x = a;
    return t;
}

int main()
{
    init();
    long j = 1;
    for(long i=1; i<=n; i++) {
        while ((!ma.empty())&&(ma.back().x<=a[i])) ma.pop_back();
        while ((!mi.empty())&&(mi.back().x>=a[i])) mi.pop_back();
        ma.push_back(rec(a[i],i));
        mi.push_back(rec(a[i],i));
        //printf("%d %d\n",ma.front().x,mi.front().x);
        while ((ma.front().x-mi.front().x)>k) {
            j++;
            if (ma.front().p<j) ma.pop_front();
            if (mi.front().p<j) mi.pop_front();
        }
        rleft[i] = i-j+1;
    }
    while (!ma.empty()) ma.pop_back();
    j = n;
    for(long i=n; i>=1; i--) {
        while ((!ma.empty())&&(ma.back().x<=a[i])) ma.pop_back();
        while ((!mi.empty())&&(mi.back().x>=a[i])) mi.pop_back();
        ma.push_back(rec(a[i],i));
        mi.push_back(rec(a[i],i));
        //printf("%d %d\n",ma.front().x,mi.front().x);
        while ((ma.front().x-mi.front().x)>k) {
            j--;
            if (ma.front().p>j) ma.pop_front();
            if (mi.front().p>j) mi.pop_front();
        }
        rright[i] = j-i+1;
    }
    mleft[1] = rleft[1];
    for(int i=2; i<=n; i++)
        mleft[i] = max(mleft[i-1],rleft[i]);
    mright[n] = rright[n];
    for(int i=n-1; i>=1; i--)
        mright[i] = max(mright[i+1],rright[i]);
    long res=0;
    for(long i=1; i<n; i++) {
        res = max(res,mleft[i]+mright[i+1]);
    }
    printf("%ld",res);
    return 0;
}

Code mẫu của RR

#include <sstream>
#include <iomanip>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <deque>
#include <complex>

#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
#define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
#define FORN(i,a,b) for(int i=(a),_b=(b);i<_b;i++)
#define DOWN(i,a,b) for(int i=a,_b=(b);i>=_b;i--)
#define SET(a,v) memset(a,v,sizeof(a))
#define sqr(x) ((x)*(x))
#define ll long long
#define F first
#define S second
#define PB push_back
#define MP make_pair

#define DEBUG(x) cout << #x << " = "; cout << x << endl;
#define PR(a,n) cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl;
#define PR0(a,n) cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl;
using namespace std;

//Buffer reading
int INP,AM,REACHEOF;
#define BUFSIZE (1<<12)
char BUF[BUFSIZE+1], *inp=BUF;
#define GETCHAR(INP) { \
    if(!*inp) { \
        if (REACHEOF) return 0;\
        memset(BUF,0,sizeof BUF);\
        int inpzzz = fread(BUF,1,BUFSIZE,stdin);\
        if (inpzzz != BUFSIZE) REACHEOF = true;\
        inp=BUF; \
    } \
    INP=*inp++; \
}
#define DIG(a) (((a)>='0')&&((a)<='9'))
#define GN(j) { \
    AM=0;\
    GETCHAR(INP); while(!DIG(INP) && INP!='-') GETCHAR(INP);\
    if (INP=='-') {AM=1;GETCHAR(INP);} \
    j=INP-'0'; GETCHAR(INP); \
    while(DIG(INP)){j=10*j+(INP-'0');GETCHAR(INP);} \
    if (AM) j=-j;\
}
//End of buffer reading

const long double PI = acos((long double) -1.0);

int n, k, a[300111];
int l[300111], r[300111];
int nn[22][300111], ln[22][300111], lg[300111];

#define TWO(x) (1<<(x))

void initRMQ() {
    // Build log
    int p = 1, now = 0;
    while (p <= 300000) {
        lg[p] = now;
        p *= 2; ++now;
    }
    FOR(i,1,300000)
    if (lg[i] == 0) lg[i] = lg[i-1];

    // Build level 0
    FOR(i,1,n) nn[0][i] = ln[0][i] = a[i];

    // Build RMQ
    FOR(t,1,20) {
        FOR(i,1,n-TWO(t)+1) {
            nn[t][i] = min(nn[t-1][i], nn[t-1][i+TWO(t-1)]);
            ln[t][i] = max(ln[t-1][i], ln[t-1][i+TWO(t-1)]);
        }
    }
}

int getMin(int i, int j) {
    int t = lg[j - i + 1];
    return min(nn[t][i], nn[t][j-TWO(t)+1]);
}

int getMax(int i, int j) {
    int t = lg[j - i + 1];
    return max(ln[t][i], ln[t][j-TWO(t)+1]);
}

int main() {
    GN(n); GN(k);
    FOR(i,1,n) GN(a[i]);
    if (n == 1) {
        cout << 1 << endl;
        return 0;
    }

    initRMQ();

    int j = 1, len, res = 0;
    FOR(i,1,n) {
        while (j < n && getMax(i,j+1) - getMin(i,j+1) <= k) ++j;

        len = j - i + 1;
        r[i] = max(r[i], len);
        l[j] = max(l[j], len);
        if (len == n) res = n;
    }

    FOR(i,2,n) l[i] = max(l[i], l[i-1]);
    FORD(i,n-1,1) r[i] = max(r[i], r[i+1]);

    FOR(i,1,n-1) res = max(res, l[i] + r[i+1]);
    cout << res << endl;
    return 0;
}