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 2 3 4 5 6 7 8 9 10 11 12 Next >

	sophozaar: 2018-01-13 11:50:24 Time limit should be reduced!! Optimised Brute force also getting AC!
	shub1025: 2017-12-28 17:44:11 10 2 47 5 2 6 9 87 4 55 466 3 try this out
	dunjen_master: 2017-12-27 21:16:42 make sure you write s.erase(s.find(a[i-k])) where s is a multiset otherwise all the occurences of a[i] will be deleted...costed me a WA
	dsri_99: 2017-12-23 06:30:25 simple idea of arrays and selection sort is enough to solve the problem.
	karthik1997: 2017-12-16 19:48:25 Using Deque with fast i/o gives u AC with 0.00s time . But Also solve it with segment trees etc :)
	arjun8115: 2017-10-06 07:29:24 easily solved using set and map...
	hitman007: 2017-09-25 21:01:59 I can see lots of people using deque and segment tree. You can try to implement it using sparse table as well (although not best example of it) https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/#Sparse_Table_(ST)_algorithm
	mahilewets: 2017-09-05 15:40:56 std::multiset
	hwojtowicz: 2017-08-23 09:58:50 What is definition for contiguous subarray in this case? Why we got duplicates of '5' in task description test (there is no 3 times of '5' in input array)?
	raichu7: 2017-07-30 03:46:37 Compilation error-->AC :)