[Python] 백준 13398 연속합 2

https://www.acmicpc.net/problem/13398

13398번: 연속합 2

문제 해결

리스트안에서 i번째에서 j번째의 합의 최댓값을 구하는 문제 BUT 중간에 하나의 수를 뺄 수 있다.

n번째 까지 연속해서 왔을 때 최댓값은 n-1번째까지 수에 영향을 받으므로 dp를 이용하면 좋겠다는 것을 알 수 있다.

이는 처음부터 n 번째 수까지 나열했을 때 n까지 연속해서 오는동안 하나의 수도 안 뺀 최댓값을 dp[n][0],

중간에 하나 뺐으면 dp[n][1]으로 정의한다.

중간에 끊어지고 다시 처음부터 시작할 수도 있다. 그러므로 dp전체에서의 최댓값을 구해야 한다.

 

CODE

import sys
input = sys.stdin.readline

n = int(input())
num = [0]+list(map(int, input().split()))
dp = [[0, 0] for _ in range(n+1)]
dp[1][0] = num[1]
ans = dp[1][0]
for i in range(2,n+1):
    dp[i][0] = max(dp[i-1][0]+num[i], num[i]) # 이어 붙이거나 새로 시작하던가
    dp[i][1] = max(dp[i-1][1]+num[i], dp[i-1][0]) #이미 중간에 하나 수를 뺐던가 지금 n번째 수를 빼던가
    ans = max(ans, dp[i][0], dp[i][1])
print(ans)