다이나믹 프로그래밍 - 백준 1912 [Python]

Problem)

 

Solution)

D[i] = i 번째 수로 끝나는 가장 큰 연속합

이렇게 식을 구했으면, i번째 수에게 가능한 경우를 세야한다.

 

따라서 A[i-1]로 끝나는 가장 큰 연속합 뒤에 A[i]가 추가된 경우라고 생각하여 문제를 풀면 된다.

 

점화식을 세워보면, D[i-1] + A[i], A[i]중 최대값을 D[i]에 넣어주면 된다.

 

Answer)

n = int(input())
a = list(map(int,input().split()))
d = [0]*(n)

for i in range(n):
    d[i] = a[i]
    if i == 0:
        continue
    if d[i] < d[i-1] + a[i]:
        d[i] = d[i-1] + a[i]
print(max(d))