기록하는 습관

[백준] DP - 연속합 본문

알고리즘/[문제풀이] 백준

[백준] DP - 연속합

로그뉴 2020. 10. 3. 19:48

www.acmicpc.net/problem/1912

 

1912번: 연속합

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

www.acmicpc.net

s[k] : max(s[k-1] + k 번째 값 vs 처음부터 다시 시작하기 (a[k]))

 

import sys

N = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))

s = [0] * N
s[0] = a[0]

for k in range(N):
    s[k] = max(s[k - 1] + a[k], a[k])

print(max(s))

'알고리즘 > [문제풀이] 백준' 카테고리의 다른 글

[삼성sw역량테스트 - 기출] 구슬 탈출2  (0) 2020.10.11
[백준] DP - 동전1  (0) 2020.10.04
[백준] DP - RGB 거리  (0) 2020.10.03
[백준] DP - 계단 오르기  (0) 2020.10.03
[백준] DP - 1로 만들기  (0) 2020.10.03
'알고리즘/[문제풀이] 백준' Related Articles more
Comments