まず、\(A\) を変更しなかった場合の、「ロボットが一度以上通る整数座標の個数」について考えます。ロボットは連続的に動くため、ロボットが到達した最小および最大の座標をそれぞれ \(l\), \(r\) とすると、ロボットは \(l\) 以上 \(r\) 以下のすべての整数座標を通っており、それ以外のどの整数座標も通っていません。さらに、ロボットはそれぞれの回の移動の途中で方向変換することはないため、ロボットが到達した最小の座標の候補は、\(0\), \(A_1\), \((A_1+A_2)\), \(\ldots\), \((A_1+A_2+\cdots+A_N)\) のいずれかです。最大についても同じことが成り立ちます。さらにこれらの座標はすべて整数であるため、結局この場合の一度以上通る整数座標の個数は、

\[ \max \left(0,A_1,(A_1+A_2),\ldots,(A_1+A_2+\cdots+A_N)\right) -\min\left (0,A_1,(A_1+A_2),\ldots,(A_1+A_2+\cdots+A_N)\right)+1 \]

となります。ここで、\(l,r\) が整数の時、\(l\) 以上 \(r\) 以下の整数は \((r-l+1)\) 個あることに注意してください。以下、\(\displaystyle\max \left(0,A_1,(A_1+A_2),\ldots,(A_1+A_2+\cdots+A_N)\right)\) を\(\displaystyle\max_{0\leq i\leq N} (A_1+\cdots+A_i)\) と表記します \(\min\) についても同様です。

次に、\(A_k\) の符号を反転した時について考えます。区別のため、反転させる前、すなわち入力で与えられる \(A_i\) を \(A^0_i\) で表し、反転後の \(A_i\) を \(A'_i\) で表すことにします。特に、\(A'_k=-A^0_k\) であり、\(i\neq k\) について \(A'_i=A^0_i\) が成り立ちます。
先と同じ議論から、このときのロボットが一度以上通る整数座標の個数は、

\[ \max_{0\leq i\leq N} (A'_1+\cdots+A'_i) -\min_{0\leq i\leq N} (A'_1+\cdots+A'_i) +1 \]

となります。ここで、\(i<k\) ならば、\(A'_1+A'_2+\cdots+A'_i=A^0_1+A^0_2+\cdots+A^0_i\) が成り立ち、\(i\geq k\) ならば、 \(A'_1+A'_2+\cdots+A'_{k-1}+A'_k+A'_{k+1}+\cdots+A'_i=A^0_1+A'^0_2+\cdots+A^0_{k-1}-A^0_k+A^0_{k+1}+\cdots+A^0_i =(A^0_1+A^0_2+\cdots+A^0_i)-2A^0_k\) が成り立ちます。

よって、

\[ \max_{0\leq i\leq N} (A'_1+\cdots+A'_i) =\max\left( \max_{0\leq i\leq k-1} (A^0_1+\cdots+A^0_i), \left( \max_{k\leq i\leq N} (A^0_1+\cdots+A^0_i) \right) -2A^0_k \right) \]

となります。 ここで、\(0\leq i\leq N\) について、\(S_i\) を \(S_i=A^0_1+\cdots+A^0_i\) で定義します。 さらに、\(1\leq k\leq N\) について、以下のように \(M^{Left}_k\), \(M^{Right}_k\), \(m^{Left}_k\), \(m^{Right}_k\), を定義します。

• \(\displaystyle M^{Left}_k= \max_{0\leq i\leq k-1} S_i\)
• \(\displaystyle M^{Right}_k= \max_{k\leq i\leq N} S_i\)
• \(\displaystyle m^{Left}_k= \min_{0\leq i\leq k-1} S_i\)
• \(\displaystyle m^{Right}_k= \min_{k\leq i\leq N} S_i\)

このとき、\(A_k\) の符号を反転した時のロボットが一度以上通る整数座標の個数は \(\max(M^{Left}_k, M^{Right}_k-2A^0_k)-\min(m^{Left}_k, m^{Right}_k-2A^0_k)+1\) となります。

よって、\(M^{Left}_k\), \(M^{Right}_k\), \(m^{Left}_k\), \(m^{Right}_k\) を高速に求めることができれば良いですが、これは以下の手順で可能です。

• \(S_0=0\), \(S_i=S_{i-1}+A^0_i\) \((1\leq i\leq N)\) を\(i\) について昇順に計算する。
• \(M^{Left}_1=S_0\), \(M^{Left}_k=\max(M^{Left}_{k-1},S_{k-1})\) \((2\leq k\leq N)\) を\(k\) について昇順に計算する
• \(M^{Right}_N=S_N\), \(M^{Right}_k=\max(M^{Right}_{k+1},S_k)\) \((1\leq k\leq N-1)\) を\(k\) について降順に計算する
• \(m^{Left}_1=S_0\), \(m^{Left}_k=\min(m^{Left}_{k-1},S_{k-1})\) \((2\leq k\leq N)\) を\(k\) について昇順に計算する
• \(m^{Right}_N=S_N\), \(m^{Right}_k=\min(m^{Right}_{k+1},S_k)\) \((1\leq k\leq N-1)\) を\(k\) について降順に計算する。

これらを用いて \(k=1,2,\ldots,N\) にわたる \(\max(M^{Left}_k, M^{Right}_k-2A^0_k)-\min(m^{Left}_k, m^{Right}_k-2A^0_k)+1\) の最大値を求めれば良いです。 どの要素の符号も反転しなかった時の値は先の定義における\(l,r\)が \(l=\min(m^{Left}_N,S_N)\), \(r=\max(M^{Left}_N,S_N)\) と書けるため、それより求まります。
よってこの問題を解くことができました。

他にも動的計画法を用いて高々 \(X\) 回反転したときの最大値を求める方法を \(X=1\) に限定して解く方法もあります（別解の実装例参照）。

C++ による解答例:

#include <bits/stdc++.h>
using namespace std;

int main(void){
	int n;
	cin >> n;

	vector<long long> a(n), s(n+1), mxl(n+1), mxr(n), mnl(n+1), mnr(n);

	for(int i=0;i<n;i++)cin >> a[i];

	s[0]=0;
	for(int i=0;i<n;i++)s[i+1]=s[i]+a[i];

	mxl[0]=s[0];
	mnl[0]=s[0];
	for(int i=1;i<=n;i++){
		mxl[i]=max(mxl[i-1],s[i]);
		mnl[i]=min(mnl[i-1],s[i]);
	}

	mxr[n-1]=s[n];
	mnr[n-1]=s[n];
	for(int i=n-2;i>=0;i--){
		mxr[i]=max(mxr[i+1],s[i+1]);
		mnr[i]=min(mnr[i+1],s[i+1]);
	}

	long long ans=mxl[n]-mnl[n]+1;
	for(int i=0;i<n;i++){
		ans=max(ans,max(mxl[i],mxr[i]-2*a[i])-min(mnl[i],mnr[i]-2*a[i])+1);
	}

	cout<<ans<<endl;
	return 0;
}

C++ による解答例（別解）:

#include <bits/stdc++.h>
using namespace std;

int main(void){
	int n;
	long long mn[2]={},mx[2]={},x=0,ans=0;

	cin>>n;
	for(int i=0;i<n;i++){
		cin>>x;
		mx[1]=max(mx[0]+abs(x),mx[1]-x);
		mn[1]=min(mn[0]-abs(x),mn[1]-x);		
		mx[0]=max(0LL,mx[0]-x);
		mn[0]=min(0LL,mn[0]-x);
		ans=max(max(ans,mx[1]),-mn[1]);
	}
	cout<<(ans+1)<<endl;
	return 0;
}