[AtCoder] ABC 182 D - Wandering

最初は愚直に解いたら時間超過してしまったので工夫しました。
$1 \le i \le N$ である $i$ のときの座標を $X_{i}$ とします。
また $i$ での移動の最大値は、$1 \le k \le i$ の中で $\sum^k_{j=1} A_{j}$ の最大値となります。
この $i$ での移動の最大値を $B_{i}$ とすると、
$i+1$ での最大値は、$X_{i} + B_{i+1}$
となります。
したがって、$i$ を動かしていって最大値を更新していけば答えが出ると考えました。
というわけで、こうすれば解けるんじゃないかというのはすぐわかって、それは解説とほぼ同じだったのですが、
そこからソースコードに落とし込むのに時間がかかってしまいました。
言語はC++(GCC 9.2.1)でAtCoderのコードテストで確認しています。

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

int main() {
  ll N, a, sum = 0, ans = 0;
  cin >> N;
  vector<ll> X(N+1, 0), B(N+1, 0);
  for (int i = 0; i < N; i++) {
    cin >> a;
    X[i+1] = X[i] + sum + a;
    B[i+1] = max(B[i], sum + a);
    sum += a;
  }
  for (int i = 0; i < N; i++) {
    ans = max(ans, X[i] + B[i+1]);
  }
  cout << ans << endl;
}