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: 2017-03-24 22:04:28

ac in one go
simple implementation of sliding window !!

rohit9934: 2017-03-08 15:54:05

Brute Force worked, i wasnt expecting that because time complexity was O((n-k)*k).Accepted appeared like Magic.

nilabja16180: 2017-03-01 19:06:47

Great application of Deque!
AC in one GO!

vladimira: 2017-02-27 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: 2017-02-11 07:15:52

Last edit: 2017-02-11 07:16:28
kshitij tripathi: 2017-02-04 09:08:34

using deque : 0.01 s , bruteforce : 0.80s :D

aman_joshi668: 2017-01-20 14:19:55

got ac with segment tree but
can someone share o(n)code mail me to amanjoshi668@gmail.com

vunnamtej: 2017-01-10 12:54:16

O(n) deque 0.04s

sandeep_4141: 2017-01-06 16:35:59

brute force and deque both are accepted but brute force is easy!!

Last edit: 2017-01-06 17:35:44
sidpatki: 2017-01-03 07:12:15

how can i see others source code?


Added by:priyamehtanit
Date:2012-02-09
Time limit:0.222s-0.972s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:own