1912. 연속합

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

1912번: 연속합

 

d[n] : a[n]을 포함하는 연속된 부분 수열들 중 그 합이 최대인 값.

 

수열이 다음과 같다고 하자.

d[0]은 자기자신 밖에없으므로 그냥 a[0]이다.

그럼 d[1]은 몇일까? 

수열이 {10, -4}이므로 원소 둘 다 더해서 10 + (-4) = 6 일수 있고, 아니면 앞의 숫자는 버리고 -4부터 시작해서 그냥 -4 일수 있다. 둘 중 큰 값은 전자 6이다.

d[2]를 보자.

수열은 {10, -4, 3}이다. 

여기서 "dp 스럽게" 생각해보자. 

d[1] 즉 {10, -4} 까지의 가장 큰 연속된 부분수열의 합이 6이다. 거기에 새로 나온 3을 더하면 9이다.

아니면 앞의 숫자를 버리고 3부터 시작할수 있다. 9와 3중 큰 수는? 9이다.

즉 d[i-1] + a[i]와 a[i]를 비교해서 큰 수가 d[i]가 된다.

이렇게 쭉 가면..

i = 7일 때를 보면.

수열은 {10, -4, 3, 1, 5, 6, -35, 12}이다. 

d[6] + a[7] = -2이다.

-2는 a[7] = 12 보다 작다. 그래서 i = 7일 때는 d[i-1] + a[i]보다 a[i]가 크다. 

그럼 앞의 숫자는 다 버리게 된다. 

 

 

d[i]를 다 채우면

d값중 가장 큰 값 33이 답이다. 수열은 {12 ,21} 인 것이다. 

 

코드

n = int(input())

a = [0] * n  # 수열 저장할 배열
d = [0] * n

a = input().split()  # 수열 입력하고 int형으로 변경 
for i in range(n):
    a[i] = int(a[i])

d[0] = a[0]
res = d[0]
# d[i-1]값과 현재 a[i]값의 합이 그냥 a[i]보다 작다면 필요가 없으니 버린다
for i in range(1, n, 1):
    d[i] = max(d[i-1] + a[i], a[i])
    res = max(res, d[i])  # 가장 큰 값 계속 갱신

print(res)