[백준 단계별 풀이 - 동적계획법] #1912 연속합

문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

입력

 

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

첫째 줄에 답을 출력한다.

 

코드

N = int(input())
arr = list(map(int, input().split()))
ref = [0 for _ in range(N)]
ref[0] = arr[0]
result = ref[0]
for i in range(1, N):
    ref[i] = max(ref[i-1] + arr[i], arr[i])
    result = max(result, ref[i])

print(result)

 

노트 

1. 연속되는 합의 많은 경우의 수에 대해서 전부 저장해놓으려고 생각해서 틀렸다. 

모두 저장하려 하지 않고, 그냥 result 변수 값을 업데이트 하니까 해결!

 

2. result 값의 초기값을 두지 않아서 틀림

 

3. result 값의 초기값을 -1001로 둬서, arr의 첫 번재 원소는 고려하지 않아서 틀림