13398: 연속합 2

• dp1은 수열에서 수를 제거하지 않은 경우의 연속합임
• dp2는 수열에서 수를 제거하는 경우의 연속합임. 이 경우에선 2가지 case를 고려해야함
• • case 1) A[i]를 제거하는 경우
• • case 2) i 이전의 index를 이미 제거하여 A[i]를 제거할 수 없는 경우
• • case 1)과 2) 중 큰 값을 dp2에 할당해줌

import sys

N = int(input())
A = list(map(int, sys.stdin.readline()[:-1].split(' ')))

if N > 1:
    dp1 = [0 for _ in range(N)]; dp1[0] = A[0]
    for i in range(1, N):
        if dp1[i-1] + A[i] < A[i]:
            dp1[i] = A[i]
        else:
            dp1[i] = dp1[i-1] + A[i]

    dp2 = [0 for _ in range(N)]; dp2[0] = A[0]
    for i in range(1, N):
        if dp1[i-1] > dp2[i-1] + A[i]:
            dp2[i] = dp1[i-1]
        else:
            dp2[i] = dp2[i-1] + A[i]

    max_1 = max(dp1); max_2 = max(dp2)
    print(max(max_1, max_2))
else:
    print(A[0])