BOJ-1912 연속합

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

문제 소개

n개의 정수로 이루어진 수열이 주어졌을 때 연속된 몇 개의 수를 선택해서 구할수 있는 가장 큰 합을 구하는 문제이다.

문제 풀이

n의 범위가 1 <= n <= 100000이기 때문에, 시간 초과에 유의하여야 한다. 만약 n번 반복하는 동시에 매 반복마다 min()을 호출하는 등으로 코드를 구성하면 점점 커지는 배열의 길이 때문에 시간초과를 초래할 것이다.

부분합 계산

수열/리스트에서 일정 구간의 합을 구하는 대표적인 방법은 부분합을 이용하는 것이다. 부분합을 담기 위한 리스트 acc를 선언하고 반복문을 통해 부분합을 계산한다.

이제 부분합끼리의 뺄셈을 통해 리스트의 특정 구간 합을 구할 수 있다. 예를 들어, acc[5] - acc[2]는 인덱스 3부터 5까지의 구간의 합을 의미한다.

유의사항

여기서 2중 반복문으로 모든 부분합을 구한 후 최대값을 max()로 구할 수는 있지만, 이렇게 풀이하면 n의 큰 범위에 2중 반복문이 더해져 시간이 초과된다.

즉, 시간 초과를 피하려면 반복문이 중첩되지 않도록 하는 동시에 구한 값을 재사용하도록 코드를 작성해야 한다.

해답 도출

리스트 mins는 특정 인덱스까지의 acc값 중 최소값을 갖는다. 예를 들어, mins[3]은 min(acc[:3])과 같다. 코드에서는 새 값을 mins의 마지막 원소와 비교하는 방식으로 min()을 사용하지 않고 구현하였다.

acc[i] - mins[i]는 인덱스 i까지의 구간합 중 최대값을 의미한다.

만약 리스트 mins를 미리 구해놓지 않고 매번 인덱스 i까지의 acc중 최소값을 구해서 계산한다면 중복된 연산으로 인해 시간초과가 발생할 것이다.

코드

import sys
input = lambda: sys.stdin.readline().rstrip()

n = int(input())
arr = list(map(int, input().split()))
acc = []        # 누적합 리스트

t = 0
for i in range(n):
    t += arr[i]
    acc.append(t)

mins = [0]      # mins[i]는 min(acc[:i])를 의미
for i in range(n - 1):
    if acc[i] < mins[-1]:
        mins.append(acc[i])
    else:
        mins.append(mins[-1])

res = [acc[0]]
for i in range(1, n):
    res.append(acc[i] - mins[i])

print(max(res))