「列のうち \(i\) 番目だけ変えたとき全体でどうなるか？ 全ての \(i\) で答えよ」系の問題は、前後から累積和を取るとうまくいくことがあります。

ロボットは連続的に動くので、行動を固定したときの答えは、行動の過程で到達する左端の座標と右端の座標から求めることができます。

前からの”累積和”として、各 \(i\) について以下の3つの量を計算します。

• \(i\) 回目の行動まででロボットが通る左端の座標
• \(i\) 回目の行動まででロボットが通る右端の座標
• \(i\) 回目の行動終了時点でロボットがいる座標

これはシミュレーションにより全体で \(O(N)\) で求めることができます。

後ろからの”累積和”として、各 \(i\) について以下の2つの量を計算します。

• \(i\) 回目以降の行動を座標 \(0\) から始めたとき、ロボットが通る左端の座標
• \(i\) 回目以降の行動を座標 \(0\) から始めたとき、ロボットが通る右端の座標

これも \(i\) の降順に全体で \(O(N)\) で求めることができます。（下図参照）

この2つの情報から「\(i-1\) 回目までの行動」「\(i\) 回目の反転した行動」「\(i+1\) 回目以降の行動」の情報を統合して結果を求めることができます。（下図参照）

実装例 (Python)

N=int(input())
A=list(map(int,input().split()))

S=[(0,0,0)]
for a in A:
  L,R,crr=S[-1]
  S.append((min(L,crr+a),max(R,crr+a),crr+a))

T=[(0,0)]
for a in reversed(A):
  L,R=T[-1]
  T.append((min(0,a,L+a),max(0,a,R+a)))
T.reverse()

ans=S[-1][1]-S[-1][0]
for i in range(N):
  L1,R1,crr=S[i]
  L2,R2=T[i+1]
  crr-=A[i]
  L=min(L1,crr,crr+L2)
  R=max(R1,crr,crr+R2)
  ans=max(ans,R-L)

print(ans+1)