[ACM] CSU 1553 Good subsequence (척 취 법)

제목 주소:http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1553
n 의 수의 서열 을 정 하고 최 장 연속 구간 이 구간 내의 최대 값 과 최소 값 의 차 이 를 만족 시 키 도록 합 니 다 < = k
(척 취 법)

const int maxn=10010;
int num[maxn];
int n,k;
int MIN,MAX;
int main()
{
    while(scanf("%d%d",&n,&k)!=EOF)
    {
        for(int i=1;i<=n;i++)
            scanf("%d",&num[i]);
        int l=1,r=1;
        MAX=MIN=num[1];
        int ans=1;
        while(1)
        {
            if(r>n)
                break;
            while(1)
            {
                MAX=max(MAX,num[r]);
                MIN=min(MIN,num[r]);
                if(MAX-MIN<=k&&r<=n)
                    ans=max(ans,r-l+1);
                if(MAX-MIN<=k)
                    r++;
                else
                    break;
                if(r>n)
                    break;
            }
            if(r>n)
                break;
            bool first=1;
            while(MAX-MIN>k&&l<r)//l   ，Max，Min     ！
            {
                l++;
                if(first)
                {
                  MAX=num[l],MIN=num[l];
                  first=0;
                }
                else
                {
                    MAX=max(MAX,num[l]);
                    MIN=min(MIN,num[l]);
                }
            }
            for(int k=l;k<=r;k++)
            {
                MAX=max(MAX,num[k]);
                MIN=min(MIN,num[k]);
            }
            if(l==r)
            {
                r++;
                MAX=max(MAX,num[r]);
                MIN=min(MIN,num[r]);
            }
        }
        printf("%d
",ans);
    }
    return 0;
}