백준 알고리즘 - 연속합 (1912) [Python]

 문제

 

www.acmicpc.net/problem/1912

1912번: 연속합

 

 

 

 

 

 문제 상황

 

- 주어진 수열에서 합이 가장 큰 연속 부분 수열의 합을 구하는 문제이다.

 

 

 

 

 

 해결 전략

1

- 범위가 100,000이므로 O(N^2)는 100억으로 속도 이슈가 발생하여 O(N) 혹은 O(NlogN)의 범위 안에서 작동하여야 한다.

 

- cache를 어떻게 정의하느냐가 문제의 포인트이다.

 

- 0부터 i 사이의 구간에서 i로 끝나는 연속 부분합 중 최대의 값을 저장한다.

 

 

 

 

 

 코드

 

from sys import stdin
input = stdin.readline
N = int(input())
N_list = list(map(int, input().split()))
cache = [0]*N # i번째 요소를 포함하는 부분 최대합 
cache[0] = N_list[0] 
max_num = cache[0]
for i in range(1, N):
    # i-1를 포함하는 연속 부분합 중 최대가 음수이면 앞부분은 어차피 버린다.
    cache[i] = max(0, cache[i-1]) + N_list[i]
    max_num = max(max_num, cache[i])
print(max_num)
 
# cache = [0]*(N+1)
# cache[1] = N_list[0]
# for i in range(1,N):
#     cache[i+1] = cache[i] + N_list[i]
# max_sum = -float('inf')
# for i in range(1,N+1):
#     for j in range(i):
#         if cache[i]-cache[j] > max_sum:
#             max_sum = cache[i]-cache[j]
# print(max_sum)

 

 

 

 

 

 해설

 

- 직접 합을 구해 그 차이를 이용하려고 하였으나 이렇게되면 O(N^2)가 된다. 그래서 필요한 것이 dp이며 연속합이므로 cache를 i-1을 포함하는 0부터 i-1 사이의 부분 수열 중 가장 합이 큰 값을 저장하는 것으로 정의한다.

 

- "더 크면 바꿔준다"

 

 

 

 

 

 새로 학습한 것 & 실수 

 

- 아직 cache를 잘 정의하지 못한다. i번째를 관찰할 때 포인트는 결국 i-1은? i-2는? 에서 그 값이 음수가 아닌 그 총합이 음수가 나오지 않는 한 계속 진행해야하므로 0보다 크다면 더해주는게 포인트이다.