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
© 2015 HUST ACMICPC TEAM. All Right Reserved.