1912: 연속합

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

1912번: 연속합

설명

n개의 정수로 이루어진 수열에서 연속된 몇 개의 수를 선택해 가장 큰 합을 출력하는 프로그램 작성. 예를들어, 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌을 때, 정답은 12 + 21 인 33이다.

핵심 아이디어

• 최대 계산 값을 계속 기록하면서, 최대한 빠른 시간 안에 해결하는 것이다.
• Memorization(기억법)을 활용하는 것으로 대표적이로 DP 스킬 중 하나이다.
• i번째 데이터 이전까지의 합을 계산하고 최댓값을 지속적으로 기록한다. 이때, 이전까지의 합이 i번째 숫자보다 작은 경우 이전의 기록들은 무의미하다. 따라서 i번째 숫자를 최댓값으로 설정한다. max() 활용

실제 작은 문제부터 계산해보면

첫 번째: Loop i = 1 인 경우, data[1] = max(-4, -4+10=6) -> data[1] = 6. 따라서 6은 이전까지 연속된 합 중 최댓값을 기록한 것이다. DP-Memorization 

data = [ 10, 6 , 3, 1, 5, 6, -35, 12, 21, -1 ]

두 번째: Loop i = 2 인 경우, data[2] = max(3, 3+6=9) -> data[2] = 9. 따라서 9는 이전까지 연속된 합 중 최댓값을 기록 한 것이다. 

data = [ 10, 6, 9 , 1, 5, 6, -35, 12, 21, -1 ]

...

이런 식으로 반복문을 돌다가 다 돌았을 때 나오는 결과는 다음과 같다.

data = [10, 6, 9, 10, 15, 21, -14, 12, 33, 32] 이고 max(data) = 33 이 정답으로 출력되는 것이다.  이런식으로 작은 문제부터 풀어보자!

코드 구현

n = int(input())

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

# 반복문을 1에서 시작하는 이유
# 이전까지 모든 숫자의 합 중 최댓값을 그때 그때 기록하는 것
# 데이터의 시작점이 0번 인덱스는 이전까지의 합이 0 자신 자체이기 때문에
# 아무런 필요가 없다.
for i in range(1, n):
	# i번째 데이터를 업데이트 하는 이유
	# i번째 인덱스는 핵심코드의 논리인 "이전까지 모든 숫자의 합 중 최댓값"
	# 이기 때문에 업데이트 해야한다. 
	data[i] = max(data[i], data[i-1]+data[i])
print(max(data))
# print(data): [10, 6, 9, 10, 15, 21, -14, 12, 33, 32]

---

반복문을 1부터 시작하는 이유는 "이전까지 모든 숫자의 합 중 최댓값"을 계속해서 기록하는 것인데, 데이터 0부터 시작하게 되면 이전까지의 합이 0이다. 따라서 0 즉, 자기 자체이기 때문에 필요가 없다. 그렇기 때문에 index 1부터 시작하는 것이다.

그리고 i번째 index는 "이전까지 모든 숫자의 합 중 최댓값"이기 때문에 업데이트를 계속 해주어야 한다.