알고리즘/백준
[백준] 1912번, 연속합 (Python)
wookcode
2021. 7. 30. 13:52
728x90
반응형
문제
https://www.acmicpc.net/problem/1912
1912번: 연속합
첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
www.acmicpc.net
코드
n = int(input())
total = list(map(int, input().split()))
dp = [0 for _ in range(n)]
dp[0] = total[0]
for i in range(1, n):
dp[i] = max(total[i] + dp[i-1], total[i])
print(max(dp))DP문제이고, 연속된 몇개의 수를 선택하여 가장 큰 값을 출력하는 문제이다.
연속된 값을 더한값이 더 클 수도 있고 더하지 않은 값이 더 클수도 있다.
1부터 확인하면서 dp에 값을 채워주면 된다.
반응형