백준 13398 연속합 2 (re)

n = int(input())
a = list(map(int, input().split()))
d1 = [0] * n
d2 = [0] * n
d1[n-1] = a[n-1]
d2[0] = a[0]
for j in range(n-2, -1, -1):
    d1[j] = a[j]
    d1[j] = max(d1[j+1] + a[j], d1[j])
for j in range(1, n):
    d2[j] = a[j]
    d2[j] = max(d2[j-1] + a[j], d2[j])

d = [0] * n
for i in range(n):
    d[i] = max(d1[i]+d2[i]-a[i], d1[i]+d2[i]-(2*a[i]))

print(max(d))

하나를 빼고 연속합을 모두 구하기엔 시간 초과
각 인덱스마다 그 수로 시작하는 연속합과 그 수로 끝나는 연속합을

~~> 처음에 마지막 for문을 구하는 방식을 ~~