No.390

$S$ はソートしておく.

$S$ の各要素をノードとするグラフを考え, $x_i$ の倍数に $x_j$ が含まれるかどうかを確認し, 含まれるならば $i \rightarrow j$ の辺を追加する.

次にこのグラフの最長パスの長さを求める. $x_i$ を最後の要素とする「良い」数列の最長の長さを $w_i$ として, $i$ から出てる辺の先のノード $j$ に対して $w_j \leftarrow \max(w_j, w_i+1)$ で更新していく.