ARRAYSUB  subarrays
Given an array and an integer k, find the maximum for each and every contiguous subarray of size k.
Input
the number n denoting number of elements in the array then after a new line we have the numbers of the array and then k in a new line
n < 10^6
k < 10^5
1 <= k <= n
and each element of the array is between 0 and 10^6
(Edited: In fact, n <= 10^5)
Output
print the output array
Example
Input: 9 1 2 3 1 4 5 2 3 6 3 Output: 3 3 4 5 5 5 6
hide comments
ashu121:
20170324 22:04:28
ac in one go


rohit9934:
20170308 15:54:05
Brute Force worked, i wasnt expecting that because time complexity was O((nk)*k).Accepted appeared like Magic. 

nilabja16180:
20170301 19:06:47
Great application of Deque!


vladimira:
20170227 20:38:14
When k<= 3 brute force is faster, this optimization speed up my solution at 15%. About NZEC in python. Read input in such way: >>>words = sys.stdin.read().split() >>>n=int(words[0]) >>>k=int(words[1]) >>>lst=map(int,words[1:n+1]) 

soumith:
20170211 07:15:52
Last edit: 20170211 07:16:28 

kshitij tripathi:
20170204 09:08:34
using deque : 0.01 s , bruteforce : 0.80s :D 

aman_joshi668:
20170120 14:19:55
got ac with segment tree but


vunnamtej:
20170110 12:54:16
O(n) deque 0.04s 

sandeep_4141:
20170106 16:35:59
brute force and deque both are accepted but brute force is easy!!


sidpatki:
20170103 07:12:15
how can i see others source code?

Added by:  priyamehtanit 
Date:  20120209 
Time limit:  0.222s0.972s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  own 