Algorithm/BOJ
[python 파이썬] 백준 1912번 연속합
징늬2
2021. 2. 2. 00:38
반응형
1912번: 연속합
첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
www.acmicpc.net
연속합을 스터디때 설명을 약간 들어서 그런지 거기서 얻은 아이디어로 문제를 풀었는데 맨땅에 헤딩식으로 풀었으면 못풀었을 것 같다.
DP에서 생명은 점화식을 떠올릴 수 있느냐 없느냐다!
(and 항상 저장을 하는 cache 공간이 필요)
n = int(input())
arr = list(map(int,input().split()))
dp = [0 for _ in range(n+1)]
dp[0]=arr[0]
for i in range(1,n):
dp[i]=max(dp[i-1]+arr[i],arr[i])
print(max(dp))
반응형