[백준] 13398 '연속합 2' 파이썬(python)

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

13398번: 연속합 2

n = int(input())
arr = list(map(int, input().split()))
dp = [[0,0] for i in range(n)]
dp[0][0] = [list[0], -999999999]

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

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

Point

• 수열 안에서 부분합 중 제일 큰 수를 만드는 것으로서 이전의 부분합 문제와 동일하다 할 수 있다.
• 따라서 dp테이블을 이용하여 합들로 채워주는 식인데, 다만 수열 중 한 숫자를 제외시킬 수 있는 조건이 달려있다.
• 이에 대해서는 또 다른 dp테이블을 이용하여 i에 도착했을 때 i가 제외되었을 때와 이전에 숫자가 제외되었을 때를 max함수 안에 넣으면서 최대값을 구하면 해결이 된다.