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.

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)

print the output array

Input:
9
1 2 3 1 4 5 2 3 6
3

Output:
3 3 4 5 5 5 6

< Previous 8 9 10 11 12 13 14 15 16 17 18 Next >

	jas.py: 2015-07-14 12:44:20 Few test cases : 7 1 2 8 4 5 2 3 3 8 8 8 5 5 7 1 2 8 4 5 2 3 4 8 8 8 5 (Copied from a comment on page 11(had go really far)...were useful to me)
	Liquid_Science: 2015-06-25 17:07:46 Segment tree & brute force with optimisations both gives tle in java -_- finally ac with dp:) O(n) Last edit: 2015-06-26 11:10:38
	Aman Parashar: 2015-06-25 11:26:47 This is bad !! Brute force should not work but works !! O(nk) - no way !! For a non increasing array it should give TLE !! Last edit: 2015-06-25 11:32:24
	Deepak Singh Tomar: 2015-06-23 21:07:56 segment tree works fine
	SangKuan: 2015-06-20 09:53:19 ac in first by dp.must has other better way
	Ooo....: 2015-06-15 21:58:14 my 150th on spoj =D
	burninggoku: 2015-06-14 22:23:43 recursion rejected....set rejected...brute force accepted.... my 23.56th !!!
	sujit yadav: 2015-06-13 13:41:45 submit with c++14 compiler coz c++ 4.3.2 gave me TLE for the same solution . simple brute force ..dont forget spaces between integers . Last edit: 2015-06-13 13:45:02
	[Mayank Pratap]: 2015-06-03 13:55:02 Brute force with optimisation .... AC ... :)
	Jerry Goyal: 2015-05-29 14:49:07 what's the fuss about?..simple bruteforce.