[알고리즘/백준] 13398: 연속합 2(python)

기존 연속합과 하나를 제거한 연속합을 비교하면 된다.

dp[0][i]는 제거하지 않고 구하는 연속합
dp[1][i]는 제거하고 구하는 연속합

dp[1][i] = max(dp[0][i-1], dp[1][i-1] + a[i])
현재 숫자를 제거한 수와, 기존 숫자를 제거한 수 중에 큰 수를 고른다.

N = int(input())
a = list(map(int, input().split()))
dp = [[0] * N for _ in range(2)]
dp[0][0] = a[0]
dp[1][0] = -1000
for i in range(1, N):
    dp[0][i] = max(dp[0][i - 1] + a[i], a[i])
    dp[1][i] = max(dp[0][i - 1], dp[1][i - 1] + a[i])
print(max(max(dp[0]), max(dp[1])))