[백준]1912 연속합 파이썬 python

문제링크

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

1912번: 연속합

 

코드

import sys
input = sys.stdin.readline
 
n=int(input())
a = list(map(int, input().split()))
d = a.copy()
 
for i in range(1,n):
    if d[i]<d[i-1]+a[i]:
        d[i] = d[i-1]+a[i]
 
print(max(d))

 

POINT

- DP로 접근

- 풀이 방법:

'연속'해야 한다는 점을 잘 생각해봐야 하여 DP로 접근하다. 

'd[i] = 현재 i번째 인덱스를 포함하여 만들 수 있는 연속된 수열의 가장 큰 합' 로 정의한다.

이후, i번째에서 '현재 i번째 상태의 합 d[i]'  vs 'i번째 값까지 연속된 수열에 포함하였을 때 합 d[i-1]+a[i] ' 을 비교하여 더 큰 값으로 갱신해준다.