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
'코딩테스트' 카테고리의 다른 글
[🥈3]백준알고리즘 11727번 : 2xn 타일링 2 (0) | 2023.11.20 |
---|---|
[🥈3]백준알고리즘 9461번 : 파도반 수열 (0) | 2023.11.19 |
[🥈1]백준알고리즘 1149번 : RGB (0) | 2023.11.16 |
[🥉1]백준 알고리즘 2775번: 부녀회장이 될테댜 (0) | 2023.11.15 |
[🥈3]백준알고리즘 9095번: 1, 2, 3 더하기 (0) | 2023.11.14 |