티스토리 뷰
1912번: 연속합
첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
www.acmicpc.net
|
1
2
3
4
5
6
7
8
|
N = int(input())
array=list(map(int, input().split()))
d=[0]*N
d[0]=array[0]
for i in range(1,N):
d[i]=max(d[i-1]+array[i], array[i])
print(max(d))
|
cs |
DP 문제.
연속 합을 저장하는 d 배열을 만들어서 각 배열을 순회할 때마다, 이전 연속 합+자기 값 vs 그냥 자기 값 해서 이 두 가지 중 큰 것을 선택하는 방식을 취하면 된다.
'Problem Solving' 카테고리의 다른 글
| [BOJ 2156] 포도주 시식 (Python3) (0) | 2021.02.23 |
|---|---|
| [BOJ 9465] 스티커 (Python3) (0) | 2021.02.22 |
| [BOJ 9019] DSLR (Python3) (0) | 2021.02.22 |
| [BOJ 9012] 괄호 (Python3) (0) | 2021.02.20 |
| [BOJ 5014] 스타트링크 (Python3) (0) | 2021.02.20 |