AtCoder Beginner Contest 182 D - Wandering【Python】

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

AtCoder ProblemsのRecommendationでDifficulty: 701、Solve Probability: 36%でした。
動作の座標の累積和を求めて、(A1), (A1 + A2), (A1, + A2 + A3)...の各ひとまとまりの動作後の座標に、それまでの座標の累積和の最大値を足したものが答えの候補になるようだと気づき解くことができました。

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

# 動作の座標の累積和
sum_A = [0]
for i in range(N):
    sum_A.append(sum_A[i] + A[i])

# (A1), (A1 + A2), (A1, + A2 + A3)...の
# 各ひとまとまりの動作後の座標のリスト
last = [0]
for i in range(N):
    last.append(last[i] + sum_A[i+1])

# 各ひとまとまりの動作後の座標にそれまでの座標の
# 累積和の最大値を足したものが答えの候補
ans = 0
max_sum_A = -10 **8 - 1
for i in range(N):
    max_sum_A = max(max_sum_A, sum_A[i+1])
    ans = max(ans, last[i] + max_sum_A)

print(ans)