SPOJ.com - Problem ARRAYSUB

ARRAYSUB - subarrays

#datastructures #sliding-window-1 #data-structure-1

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

Submit solution!

hide comments

< Previous 11 12 13 14 15 16 17 18 19 20 21 Next >

	(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†): 2014-07-16 22:31:02 I don't know O(n) solution for this problem yet, but my O(nlog n) is 0.03s :-P Last edit: 2014-12-29 13:55:17*
	zicowa: 2014-07-16 20:45:02 Hello Coders !! I know you all are doing great !! O(nlog(n)) solution can be easily think for this problem but there exists a O(n) solution for this problem think for O(n) solution you will surely learn something my last submission is on the same algo . and you dont believe it is the smallest code among all :D Last edit: 2014-12-29 13:55:34
	Saurav Sharma: 2014-07-01 08:43:30 brute force method get rejected
	agaurav77: 2014-05-31 15:57:02 Good Question! O(nk) definitely works, but remember not to make your code O(nk) for all cases. It should be worst case O(n*k).
	free mind ;): 2014-04-14 20:33:59 done in 0.09 with O(n*k) finally !
	Vlad Mosko: 2014-03-02 18:26:46 NlogN is really easy.
	appy: 2014-01-11 21:13:53 anyone help with the whitespaces in input e.g 9 <--- this white space 1 2 3 1 4 5 2 3 6 please and is there space or \n after the last output?????
	appy: 2014-01-11 17:10:55 is there any whitespace means after 9 <--- this line i m getting wrong answer again and again...please sum1 help
	shashank: 2014-01-05 21:06:00 Interesting Same implementation in java got NZEC but in C++ got AC .... Sometimes java sucks ....
	pika_pika: 2013-12-31 15:32:09 those who are getting WA in the 5th test case try cases with k = 1 eg 5 2 8 4 3 6 1 worked for me considering this.

Submit solution!

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