https://www.acmicpc.net/problem/1912
1912번: 연속합
첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
www.acmicpc.net
dp를 이용하면 쉽게 풀 수 있는 문제입니다.
연속되는 수열의 최대 합이기 때문에 처음부터 더하다가
중간에 큰 수가 나오면 이전까지 더한 것을 버리면 됩니다.
n = int(input())
seq = list(map(int, input().split(' ')))
dp = seq
for i in range(1, n):
dp[i] = max(dp[i-1]+dp[i], dp[i])
print(max(dp))'백준 알고리즘' 카테고리의 다른 글
| 파이썬) 백준 알고리즘 | 9660번 : 돌 게임 6 (0) | 2022.06.30 |
|---|---|
| 파이썬) 백준 알고리즘 | 1699번 : 제곱수의 합 (0) | 2022.06.30 |
| 파이썬) 백준 알고리즘 | 11726번 : 2×n 타일링 (0) | 2022.06.30 |
| 파이썬) 백준 알고리즘 | 16120번 : PPAP (0) | 2022.06.30 |
| 파이썬) 백준 알고리즘 | 2670번 : 연속부분최대곱 (0) | 2022.06.28 |
댓글