問題で与えられた操作の代わりに、次のような操作を考えます。

• \(i\) を選び、\(A_i,A_{i+1}\) からそれぞれ \(1\) を引く。操作後も値は \(0\) 以上である必要がある。

この操作は元の操作を完全に包含しています。 よって、この操作が行えると仮定した場合の答えは、元問題の答え以下になります。 そして実はこの \(2\) つの答えは一致します。

新しい操作を使った場合の最適解を一つ適当に取ります。 最終的に \(0\) にならない項の間で何が起こるか観察します。 \(A_x>0,A_y>0,A_i=0\) (\(x<i<y\)) が最終的に達成されたとします。

ここで、\(A_i,A_{i+1}\) に対する操作を行う回数を \(v_i\) とおくことにします。 \(v_x,v_{x+1},\cdots,v_{y-1}\) の最小値が \(0\) になるように最適解を変形できることを示します。

\(v_x,v_{x+2},v_{x+4},\cdots\) を \(1\) 増やし、\(v_{x+1},v_{x+3},\cdots\) を \(1\) 減らすことを考えます。 このとき、\(A_i\) (\(x<i<y\)) の値は変化しません。 また、\(A_x,A_y\) の値は高々 \(1\) しか変化しません。 この変更を可能な限り繰り返します。\(A_x,A_y\) のいずれかが \(0\) になると、よりよい解が得られてしまうため元が最適解であったことに矛盾します。よって、いずれかの \(v_i\) が \(0\) になります。 これは欲しかった解の形です。

操作回数が \(0\) 回のところで、数列を分割してみます。 すると、最終的に \(0\) にならない要素は高々 \(1\) 個です。 ここで、数列の左端と右端から値を \(0\) に合わせていくことを考えます。 するとこれは、隣接項の min を引く操作になっているとわかります。

以上より、min を引く操作を \(1\) を引く操作に置き換えてよいです。

まずはこれをDPで解くことを考えます。 先頭から見ていって、\(dp[i][j]=(A_i=j\) となる場合に先頭 \(i-1\) 項にある \(0\) の個数の最大値\()\) として計算すればよいです。 もちろんこれでは間に合わないのでさらに考察が必要です。

\(dp[i][j]\) で重要なのは、固定された \(i\) に対して \(dp[i][j]\) の値が最大となる \(j\) だけだとわかります。 それ以外の \(j\) を使う解が後々有利になることがないことが、DP の遷移を観察するとわかります。 また最大を達成する \(j\) が区間をなすことも確認できます。 よって、この区間と \(dp[i][j]\) の最大値を順に更新していけばよいです。

計算量は \(O(N)\) になります。

実装例