No.209

$A_i$ を頂点として $A_i$ の右側に題意を満たす部分列が最長いくつになるかを $R(i, v)$ とおく. ただし, $v$ は許される最大の傾きである.

このとき,

$$R(i, v) = \max_{j \gt i} R(j, A_i - A_j) \ (0 \leq A_i - A_j \lt v)$$

となる. また, $u \gt A_i$ のとき, $R(i, u) = R(i, A_i)$ である. これをメモ化再帰で計算する.

$A_i$ の左側も同様に計算する.

$i$ を $1 \dots N$ まで動かして最大の長さを求める.