Smooth Subsequence

题目描述

给定长度为 $N$ 的序列 $A = (A_1, A_2, \ldots, A_N)$。 找出 $A$ 的一个子序列的最大长度，使得任意相邻两项的绝对差不超过 $D$。 序列 $A$ 的子序列是指可以通过删除 $A$ 中的零个或多个元素并保持剩余元素原有顺序得到的序列。

输入格式

输入采用标准输入，格式如下： $N$ $D$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

输出答案。

4 2
3 5 1 2

3

5 10
10 20 100 110 120

3

11 7
21 10 3 19 28 12 11 3 3 15 16

6

提示

$1 \leq N \leq 5 \times 10^5$ $0 \leq D \leq 5 \times 10^5$ $1 \leq A_i \leq 5 \times 10^5$ 所有输入值均为整数。序列 $A$ 的子序列 $(3, 1, 2)$ 相邻项之间的绝对差最多为 $2$。

标签: AtCoder|abc339E

来源

AtCoder|abc339E