본문 바로가기
코딩테스트

[🥈2]백준알고리즘 1912번 : 연속 합

by 블루베리크림치즈쿠키 2023. 11. 18.
320x100

문제바로가기

연속합

 

 

1. 문제:

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

2. 입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

3. 출력:

첫째 줄에 답을 출력한다.

4. 풀이:

 

import sys

n = int(input())
lst = list(map(int,input().split()))
for i in range(1,n):
    lst[i] = max(lst[i], lst[i] + lst[i-1])
print(max(lst))

 

투포인터를 생각했지만 시간초과 날게 뻔했다.

 

그 다음 아이디어는 어차피 앞에서 부터 계산해봤자 음수가 나오면 필요없다.

 

그래서 현재 위치랑, 이전 위치에 합이 양수이면 최댓값으로 저장한다. 

 

예를들어

1,2,3,4,5,6,-25 ,5,6,7

이런식이면

앞에서 6까지 다 더해서 쭉 dp에 저장되지만 결국 -25 땜에 음수가 된다 

앞에 더한 21과 -25가 만나 -4 가 되고 

-4 와 -25 중 큰 값인 -4가 저장된다.

그 다음은 -4+5 보다 그냥 5가 더 크므로 5 저장인된다.

 

320x100