この解説はユーザー解説です。

最大になるのが \(A_i\) ならば、\(i\) は端（\(i=1\) または \(i=M\)) であるか、端でなく \(A_{i-1}\leq A_i \geq A_{i+1}\) であるかです。\(A_{i-1}\leq A_i \geq A_{i+1}\) は \(B_i \geq 0\) かつ \(B_{i+1} \leq 0\) と同値です。よって、\(B_i \geq 0\) かつ \(B_{i+1} \leq 0\) となる \(i\) をすべて探して、その \(A_i\) を実際に計算し最大値を求めれば良いです。実際にそのような \(i\) は無視できるものを除けば以下の議論により \(N\) 個以下になります。

数列 \(B\) は \(C\) が同じ値になっている範囲では単調増加か単調減少か一定です。(\(B_i\) が \(i\) の一次式か定数で表されるため）

• 単調減少なら \(B_i \geq 0\) かつ \(B_{i+1} \leq 0\) となる \(i\) が \(1\) つ存在する可能性があり、割り算で求められます。

• 一定ならずっと \(B_i=0\) になっている可能性がありますが、\(A\) の値が変わらないということなので無視して良いです。ずっと \(B_i =k (k \neq 0)\) なら \(B_i \geq 0\) かつ \(B_{i+1} \leq 0\) にはなりません。

• 単調増加なら \(B_i \geq 0\) かつ \(B_{i+1} \leq 0\) となる \(i\) はありません。

計算量は \(O(N)\) です。