[백준] 1912번 연속합 DP - 파이썬

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

 

일단 DP에서 값을 계속 더해 가면서 선택, 선택 안함 유형으로 풀이했다.

다음 값을 계속 더해나가되 계속 양수이면 이어서 연속으로 합을 구한다. 하지만 음수가 되버리면 최대값의 조건이 깨지므로 0으로 초기화 한다.

 

N = int(input())
lst = [0] + list(map(int, input().split()))
dp = [0] * (N+1)

if max(lst[1:]) < 0:
    ans = max(lst[1:])
else:
    for i in range(0, N+1):
        dp[i] = max(0, dp[i-1] + lst[i])
    ans = max(dp[1:])
print(ans)