[백준][Python] 13398 연속합 2

n = int(input())
lst = list(map(int, input().split()))

# 원소 제외 없는 결과, 원소 하나 제외한 결과
dp = [[0, 0] for _ in range(n)]
# 초깃값 : 나자신 or 나를 제외한 경우.
dp[0] = [lst[0], -999999999]

for i in range(1, n):
    # 끊고 출발하거나 이전에꺼에 덧붙히거나.
    dp[i][0] = max(dp[i - 1][0] + lst[i], lst[i])
    # 이전까지의 합에 나를 제외한 경우.(+0이 생략된 값을 이어붙힘), 이전까지의 합에 나를 붙힌경우(생략x)
    # => 앞에서 -가 생략이 됐고 그게 최적이라면 dp[i-1][1]+lst[i]가 더 커야하고 아니라면 
    # 앞의 생략이 최적이 아니므로 dp[i-1][0]의 생략 안된 값을 가져와 나를 생략하고 저장하게 됨.
    # 즉 생략 안된 list로 부터 나를 제외 한 값과 아닌 값을 유지해 나가며 비교하면 최적값을 구할 수 있음.  
    dp[i][1] = max(dp[i - 1][0], dp[i - 1][1] + lst[i])

ans = -999999999
for i in range(n):
    ans = max(ans, dp[i][0], dp[i][1])
print(ans)

처음에 dp[i-1][0]+0과 dp[i-1][1] + lst[i]를 이용해 이전에 제외했던 값들에 대해 컨트롤 할 수 있다는 아이디어를 깨닫지 못해 개 노다가 하고 결국 시간초과..결국 나를 제외할껀지 이전까지의 합을 쓸껀지 연속합을 끊을껀지 말껀지 두가지만 생각하면 됐던 문제.