[BOJ] 1912 - 연속합

[BOJ] 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보다 작거나 같은 정수이다.

출력

첫째 줄에 답을 출력한다.

예제 입력

10
10 -4 3 1 5 6 -35 12 21 -1

예제 출력

33

문제 해결

조금 접근이 어려웠던 문제였는데 단순하게 생각해서 힌트를 얻게되었다. 우선 입력을 담는 arr 배열과 그 수 까지를 포함했을 때의 최대 합을 담는 배열인 dp를 선언하였다.

index	0	1	2	3	4	5
arr	10	-4	3	1	5	6
dp	0	0	0	0	0	0

예시 수는 10 -4 3 1 5 6 이다.

index가 0인 경우
index가 0인 경우에는 dp에 연속 최대 합은 arr[0]이다.

if i == 0 :
    dp[i] = arr[i]

index가 1 이상인 경우를 천천히 생각해보겠다.

index가 1인 경우
두개의 값을 비교를 해봐야 한다. answer[1]의 값인 -4와 , dp[1-1]+arr[1]의 더한 값인 6을 비교해본다. 따라서 index 1까지의 연속된 최대합은 6이 된다.

index	0	1	2	3	4	5
arr	10	-4	3	1	5	6
dp	10	6	0	0	0	0

index가 2인 경우
index 2인 경우도 똑같이 현재 자신의 값까지 더한 최대 값과, 현재의 값을 비교한다.
9와 3을 비교했을때 9가 크므로 dp[2] 에는 최대합 9가 들어가게 된다.

이떄 헷갈리지 말아야 할점은 dp의 저장하는 값은 그 index 까지 연결된 최대합이라는 점이다. 처음에는 음수를 만나게 되면 어떻게 처리해야하는지 고민하게 된다. index 1 처럼 생각하면 결국 음수여도 연결된 최대 합을 dp에 저장해 놓으면 다음 index 에서도 전 인덱스의 dp 값이 연결되었을떄 최대합 이므로 똑같이 계산이 가능하다.

코드로 작성해보자.

python 코드

n = int(input())
arr = list(map(int, input().split()))
dp = [0] * n

for i in range(0, n):
    if i == 0 :
        dp[i] = arr[i]
    else :
        dp[i] = max(arr[i], arr[i]+dp[i-1])

print(max(dp))

느낀점

느낌은 이해했는데 머리가 이해하지 못했을때 글을 쓰는게 제일 어렵다.