문제
연속된 날의 수익 배열이 주어질 때, 연속 부분 배열의 합 중 최댓값을 구하라.
입력
여러 테스트 케이스가 주어지며, 각 케이스에 날 수 N과 각 날의 수익이 주어진다. N=0이면 종료.
출력
각 테스트 케이스마다 최대 부분 배열 합을 출력한다.
예제
| 입력 | 출력 |
|---|---|
6 -3 4 9 -2 -5 8 0 | 14 |
풀이
카데인 알고리즘(Kadane's Algorithm)으로 최대 부분 배열 합을 구한다.
- 현재까지의 부분합
tmpSum과 전체 최댓값maxSum을 관리한다 - 각 원소에 대해, 이전 부분합에 더하는 것과 새로 시작하는 것 중 큰 쪽을 선택한다
- 매 단계에서
maxSum을 갱신한다
핵심 아이디어: 최대 부분 배열 합은 각 위치에서 "이전 부분합을 이어갈지, 새로 시작할지"만 결정하면 O(N)에 구할 수 있다.
코드
import sys
input = sys.stdin.readline
def solution(n):
p = [int(input()) for _ in range(n)]
maxSum = -10000
tmpSum = 0
for i in range(n):
if tmpSum + p[i] > p[i]:
tmpSum += p[i]
else:
tmpSum = p[i]
maxSum = max(maxSum, tmpSum)
return maxSum
while True:
n = int(input())
if n == 0:
break
print(solution(n))복잡도
- 시간: O(N)
- 공간: O(N)