문제링크
https://www.acmicpc.net/problem/1912
1912번: 연속합
첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
www.acmicpc.net
코드
|
1
2
3
4
5
6
7
8
9
10
11
12
|
import sys
input = sys.stdin.readline
n=int(input())
a = list(map(int, input().split()))
d = a.copy()
for i in range(1,n):
if d[i]<d[i-1]+a[i]:
d[i] = d[i-1]+a[i]
print(max(d))
|
cs |
POINT
- DP로 접근
- 풀이 방법:
'연속'해야 한다는 점을 잘 생각해봐야 하여 DP로 접근하다.
'd[i] = 현재 i번째 인덱스를 포함하여 만들 수 있는 연속된 수열의 가장 큰 합' 로 정의한다.
이후, i번째에서 '현재 i번째 상태의 합 d[i]' vs 'i번째 값까지 연속된 수열에 포함하였을 때 합 d[i-1]+a[i] ' 을 비교하여 더 큰 값으로 갱신해준다.
'Algorithm > Baekjoon' 카테고리의 다른 글
| [백준] 14501 퇴사 파이썬 python (0) | 2022.02.15 |
|---|---|
| [백준] 1699 제곱수의 합 파이썬 python (0) | 2022.02.14 |
| [백준]11053 가장 긴 증가하는 부분 수열 14002 가장 긴 증가하는 부분 수열 4 파이썬 얕은 복사 python (0) | 2022.02.09 |
| [백준]2193 이친수 파이썬 python (0) | 2022.02.09 |
| [백준]10844 쉬운 계단 파이썬 python (0) | 2022.02.08 |