Maximum Of K- size subarrays (Deque)

 Problem:-

Given an array A of size 'N' and an integer k, find the maximum for each and every contiguous subarray of size k.

Input :

• First line contains 2 space separated integers 'N' and 'k' .
• Second line contains 'N' space separated integers denoting array elements.

Output:

• Space separated Maximum of all contiguous sub arrays of size k.

Constraints :

• 1<= N <=10^5
• 1<= Ai <=10^9
• 1<= k <=N

SAMPLE INPUT

 

9 3
1 2 3 1 4 5 2 3 6

SAMPLE OUTPUT

 

3 3 4 5 5 5 6

Explanation

First Sub array of size 3 : 1 2 3, here maximum element is 3

second Sub array of size 3 : 2 3 1, here maximum element is 3

third Sub array of size 3 : 3 1 4, here maximum element is 4

fourth Sub array of size 3 : 1 4 5, here maximum element is 5

Fifth Sub array of size 3 : 4 5 2, here maximum element is 5

Sixth Sub array of size 3 : 5 2 3, here maximum element is 5

Seventh Sub array of size 3 : 2 3 6, here maximum element is 6

Time Limit:1.0 sec(s) for each input file.

Memory Limit:256 MB

Source Limit:1024 KB

BEST SUBMISSION

SIMILAR PROBLEMS

CONTRIBUTORS

Code:-

#include<stdio.h>

int main()

{

    long int n,k;

    scanf("%ld%ld",&n,&k);

    long long int a[n],i,j,max;

    for(i=0;i<n;i++)

     scanf("%lld",&a[i]);

    for(i=0;i<=n-k;i++)

    {

        max=0;

        for(j=i;j<i+k;j++)

        {

if(max<a[j])

         max=a[j];

        }

        printf("%lld ",max);

    }

    return 0;

}