백준 : 1912번, 연속합

문제 주소 : www.acmicpc.net/problem/1912

정답 비율 : 30.224% (2021.03.17 21:48 기준)

1912번: 연속합

 

문제 조건 :

입력 : N개의 수(K)가 주어집니다. (N : 1 ~ 100000, K : -1000 ~ 1000)

출력 : 연속된 n 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 출력하면 됩니다.

시간 : 1초

 

문제 풀이 :

DP문제입니다. 아이디어는 다음과 같습니다.

 

1. 왼쪽부터 데이터를 하나씩 처리합니다.

2. 자신의 왼쪽 데이터의 합(sum)이 음수이면 sum을 자신의 값을 초기화하고 양수이면 자신의 sum에 더합니다.

3. 현재 최대 값과 sum의 값을 비교하여 최댓값을 경신해줍니다.

 

예시로 

-1 2 4 -8 5 6 인상 황에서

1) -1 데이터를 처리할 때 sum은 -1입니다. 최댓값 또한 -1이 됩니다.

2) 2 데이터를 처리할 때 2 입장에서는 sum을 추가해서 가는 것은 가치 손상이 발생합니다. 따라서 sum을 2로 초기화합니다. 이때 최댓값은 2가 됩니다.

3) 4 데이터를 처리할 때 4 입장에서는 sum이 양수이므로 무조건 데리고 가야 가치 증가합니다. 따라서 sum에 더하여 6이 되고 최댓값은 6이 됩니다.

4) -8 데이터를 처리할 때 -8 입장에서는 sum이 양수이므로 무조건 데리고 가야 가치 증가합니다. 따라서 sum에 더하여 -2가 되고 최댓값은 6으로 유지됩니다.

5) 5 데이터를 처리할 때 5 입장에서는 sum이 음수이므로 데리고 가는 것은 가치 손상이 발생합니다. 따라서 sum을 5로 초기화하고 최댓값은 6으로 유지됩니다.

6) 6 데이터를 처리할 때 6 입장에서는 sum이 양수이므로 무조건 데리고 가는 것이 이득입니다. 따라서 sum에 더하여 11이 되고 최댓값은 11로 갱신됩니다.

 

코드는 다음과 같습니다.

 

Python3

# solve 1912

n = int(input())
Num = list(map(int, input().split()))
Max = -1000 * 100000
Sum = 0

for i in range(n):
    Sum = Sum + Num[i] if Sum > 0 else Num[i]
    Max = max(Sum, Max)

print(Max)

 

-> -1000 * 100000 문제에서 주어지는 최솟값이므로 해당 수로 하였습니다. (사실 -1000 해도 됩니다.)