Sliding Maximum
For every k continuous numbers in an array, print the largest number. This challenge is easy to "brute-force", but see if you can find the optimal solution.
- Simple Solution: O(nk)
- Better Solution: O(n log k)
- Optimal Solution: O(n)
The provided boilerplate takes 2 parameters: an array, and the special number k.
Output
Print the largest number for each k numbers. Print all the numbers for each case on their own line.
Sample
Input:
1 7 3 1 3 5 7 9 2
Output:
5 7 9 9
The first number is k, which is 3 in this case. The output is the largest number for each group of 3 numbers in the list:
3 numbers | Largest |
---|---|
1 3 5 | 5 |
3 5 7 | 7 |
5 7 9 | 9 |
7 9 2 | 9 |
Input
Not using the provided boilerplate? Here's the input format:
The first line of input will contain t. t test cases follow, with each case consisting of n, followed by a line with n numbers. The first number on that line is k, and the remaining numbers are the list.
Challenge
Print out the largest of every k numbers in each case.
Please sign in or sign up to submit answers.
Alternatively, you can try out Learneroo before signing up.
Comments
Konstantine Muradov
Jan 29, 9:20 AMGood time of day Admins .
I have a question - how can I use Stack or Queue for this challenge ? Or it is not necessary?
Learneroo
Jan 29, 9:42 AMThe simple optimal solution uses a queue, but you can also use less optimal solutions (with a longer running time).
Anudeep Paturu
Dec 13, 4:49 AMWhy there is no cheat available for the problems?