D - Wandering

・問題URL

https://atcoder.jp/contests/abc182/tasks/abc182_d

・発想

・ぜんぶでN²/2回くらい動くのでシミュレーションは無理。
・最初見たとき「累積和の累積和」的なものをN種類求めてうまくいくのでは？と考えたが間違い。なぜなら各動作の終わりで最大になるとは限らないから。

・解法

各動作を独立として考えたとき、移動前と後の相対座標の最大値をそれぞれ別で求めておく。今の座標＋その最大値が答えか？それとも一回動作をすべてやった時の座標＋次の最大値が答えか？を一重ループで求める。

・コード

int main(){

 int N;
 cin>>N;
 vector<ll>A(N),SUM(N+1),Max(N+1);
 ll sum=0;
 rep(i,N){
   cin>>A[i];
   sum+=A[i];
   SUM[i+1]=sum;
   Max[i+1]=MAX(Max[i],SUM[i+1]);
 }
 
 ll ans=0,now=0;
 for(int i=1;i<=N;i++){
   ans=MAX(ans,now+Max[i]);
   now+=SUM[i];
 }

 cout<<ans<<endl;
   
}