1022 - K-diff subsequence
Time Limit : 5 Second
Memory Limit : 128 MB
Submission: 246
Solved: 79
- Description
- If the difference between any two adjancent elements in a sequence is not more than K, then we call this sequence is a K-diff sequence.
A subsequence of some sequence is a new sequence which is formed from the original sequence by deleting some of the elements without changing the order.
For example, "1 3 4 6" is a 2-diff subsequence of "1 2 3 4 5 6 7".
Now give you K and a sequence whose length is N, try to find out the maximum length of the K-diff subsequence of the original sequence. - Input
- The first line contains a integer T, which means there are T test cases.
For each test case: The first line contains two integers: N(0 < N < 102400), K(0 <= K < 100000).
The second line contains n positive integers: the orginal sequence.
- Output
- For each test case: Output only one line with the maximum length of the K-diff subsequence.
- sample input
-
2 5 2 1 3 2 2 3 5 2 1 3 4 7 2
- sample output
-
5 4
- hint
- " n positive integers " 0< X <2^31
- source
- lshmouse