No.489

$i$ 日目に買ったとすると, 得られる利益の最大値は $\max_{j=i+1}^{i+D}(x_j) - x_i$ である.

区間内の最大値を返す Sparse Table に $\{ x_i \}$ を入れておくことで $\max$ の計算を高速化できる.

これをすべての日で試し, 得られる利益が最大となるときの購入日と利益を求める.

売却日は購入日と利益から計算できる.