版权声明
本题版权归 Long Long OJ 所有。
题目描述
给定一个长度为 n 的序列 a1,a2,⋯,an。寻找满足以下条件的 a 的子序列 b 的最长长度:b 中最大值与 b 中最小值的差小于等于给定的整数 k。
序列 a 的子序列指删除 a 中若干个元素(可能是 0 个) 后重新把剩下的元素按原来的顺序排列得到的序列。一个序列有多个子序列。
输入格式
- 第一行:两个正整数 n,k。
- 第二行:n 个整数,第 i 个是 ai。
输出格式
一行一个正整数,表示答案。
样例
5 12
60 10 33 46 21
2
5 100
18 -14 -114 19 -81
4
提示
样例 1 解释:
选出的最长子序列是 [10,21] 或 [21,33],长度都为 2。
样例 2 解释:
选出的最长子序列是 [18,−14,19,−81],长度为 4。此外,ai 可能是负数。
- 对于 10% 的数据,1≤n,ai≤10;
- 对于 20% 的数据,1≤n≤20;
- 对于 55% 的数据,1≤n≤5000;
- 对于另外 5% 的数据,ai≥1;
- 对于 100% 的数据,1≤n≤2×105,−109≤ai≤109,0≤k≤2×109。