Sliding Maximum


Collapse Content

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

Contact Us