[백준/Python(파이썬)] 13398 연속합2

문제 : www.acmicpc.net/problem/13398

13398번: 연속합 2

연속합과 다른 조건은 수열에서 수를 하나 제거할 수 있다는 점임

그래서 dp를 차원을 두 개 두고 구현하던데 나는 그냥 리스트 두개로 구현함

[소스코드]

n = int(input())
a = list(map(int, input().split()))
dp1 = [0 for _ in range(n)]
dp2 = [0 for _ in range(n)]
dp1[0] = a[0]
dp2[0] = -999999999
result = -999999999
for i in range(1, n):
    dp1[i] = max(a[i], a[i]+dp1[i-1])
    dp2[i] = max(dp1[i-1], dp2[i-1]+a[i])

for i in range(n):
    result = max(result, dp1[i], dp2[i])
print(result)

github.com/jisun1125/algorithm-problem-solving/blob/main/baekjoon/no_13398.py