[백준] 1912 연속합 - DP (Python)

 

조건

1. 연속된 몇 개의 수일지는 모른다. (한 개 이상 선택)

2. 연속된.

3. 최대 합을 구해야 한다.

 

부분합을 구해서 dp 배열에 부분합의 max 값을 갱신해주고 그 dp 배열의 max 값을 구하면 최대 합이 구해진다. 

d[i-1] + list[i] 는 현재 원소 i 를 포함하는 최댓값의 후보이다. d[i-1] 에 list[i] 를 더한 게 현재 원소 보다 크다면 계속 더해나가는 것이 최댓값이 유지가 되는 것이고 d[i-1] 에 list[i] 더한 게 list[i] 보다 작다면 d[i-1] 는 음수라는 것이고 그러면 list[i] 부터 새롭게 연속합을 시작해야 한다. 

n = int(input())
list = list(map(int,input().split()))

dp = [0] * n

for i in range(n) :
    dp[i] = max(list[i], dp[i-1] + list[i])
    
print(max(dp))

 

 

추가

문제를 풀고 내가 맞게 풀었는지 블로그를 참고하는 과정에서 읽은 점이다. 보통 dp 리스트를 해당 인덱스까지의 최댓값을 속 갱신시켜나가는 경우가 많다. 하지만, 이 문제에서의 dp 는 해당 인덱스를 포함하는 값 중에 최댓값을 갱신시켜 나간다.