Beautiful Subsequence solution codechef
An arrayconsisting of integers is called -beautiful if it holds the following property: The number of adjacent indices with different values is at most . More formally, there are at most indices ( ) such that . Note that according to this definition, if an array is -beautiful, then is also -beautiful.
You are given an arrayconsisting of integers and an integer . Find the length of the longest -beautiful subsequence of , where a subsequence is defined below.
For example, consider the array. The subsequences and are -beautiful, and the subsequences and are -beautiful.
- A sequence is a subsequence of a sequence if can be obtained from by deletion of several (possibly, zero) elements. For example, is a subsequence of and , but not a subsequence of and .
The first line contains an integer– the number of test cases. Then test cases follow.
The first line of each test case contains two integers, – the length of array and the parameter for a beautiful sequence.
The second line of each testcase containsintegers .
For each test case, output the maximum possible length of a-beautiful subsequence of .
Sample Input 1
4 4 1 1 1 2 3 9 2 1 2 3 2 4 5 6 7 5 5 5 1 1 1 1 1 10 1 1 2 1 2 1 2 1 2 1 2
Sample Output 1
3 5 5 6
Test Case 1 : You can either chooseor as a subsequence. Both of the subsequences are -beautiful. So the maximum length of a -beautiful subsequence is .
Test Case 2 : It is optimal to choose the subsequence. So the maximum length of a -beautiful subsequence is .
Test Case 3 : You can choose the entire array as a subsequence because the given array is-beautiful for any , which includes .