[백준] 1912 - 연속합 in 파이썬

문제 출처

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

출력

첫째 줄에 답을 출력한다.

---

문제 풀이

가장 큰 수의 연속합을 얻기 위해서는

• 양수 + 양수 -> 당연히 합해야 하고,
• 양수 + 음수 -> 합해야할 수도 있고, 합하지 않아야할 수도 있다.

 (양수) + (음수)의 합 은 양수일 수도 있고 음수일 수도 있기 때문이다.

 

 

 만약 두 수의 합이 양수라면, 양수 a + 양수 b > 양수 b 는 언제나 성립하기 때문에 연속합을 끊지 않고 계속 합을 이어가는게 이득일 수밖에 없다.

 

 즉, 계속해서 연속합을 구하다가 합의 결과가 음수가 되면 연속합을 끝내고 새로운 연속합을 구하기 시작하고, 합의 결과가 양수가 되면 계속해서 연속합을 구하면 되는 것이다.

 

 

수도코드

1. n을 입력받는다
2. n의 길이를 갖는 arr 리스트를 입력받는다
3. n의 길이를 갖는 dp 리스트를 만든다 (수의 최소값인 -1000으로 초기화)
4. arr 를 순회하면서 dp 리스트에 연속된 합을 기록한다
   1. dp[i] = max { dp[i-1] + arr[i]
                            arr[i]      // dp[i-1] + arr[i] < arr[i] 라면, arr[i]부터 연속합을 다시 구하는게 더 큰 값을 얻을 수 있기 때문
5. 순회가 끝나면, 기록한 dp 리스트의 값 중에서 가장 큰 값을 정답으로 출력한다

 

 

- 풀이과정 예시 -

 

 

작성 코드

n = int(input())
arr = list(map(int, input().split()))
dp = [-1000 for _ in range(n)]

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

print(max(dp))