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
|
code_aim:
2017-07-01 19:48:26
0.01s |
|
iceelement:
2017-06-30 10:33:22
AC in one, using dp and deque |
|
mangalnimish:
2017-06-29 13:19:39
Wrong answer on judge 5..Please help |
|
itachi_2016:
2017-06-23 21:56:07
Used segtree and got AC but 0.07s not nice though |
|
sagnik_66:
2017-06-01 12:47:55
Interesting problem... 1st used Brute Force, Then used DP in O(n)! |
|
arvind002:
2017-05-31 22:18:54
Try using Deque.
|
|
ashu121:
2017-03-24 22:04:28
ac in one go
|
|
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!
|
|
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]) |
| 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 |
RSS