\(dp_{i,j}\) を\(S_i\) まで見てこれまでの移動操作で右に行く操作を \(j\) 回行っている時の幸福度の最大値と定義します。これまでの移動操作の個数を\(c\)とすると現在の座標は\(2j-c\)となります。
\(dp_{i-1}\)から\(dp_{i}\)への更新は

• \(dp_{i,j}=max(dp_{i-1,j},dp_{i-1,j-1})\)
• \(dp_{i,j}=dp_{i-1,j}+aj+b\)

と表せます。この二つはいずれもSlope Trickによって実現できます。
実装例(対称性より最大値=-最小値を用いています。)