알고리즘/동적 계획법(Dynamic Programming)

백준-1912-연속합

easysheep 2024. 4. 3. 17:46

1. 문제 출처

https://www.acmicpc.net/problem/1912

 

1912번: 연속합

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

www.acmicpc.net

2. 풀이

DP방법중 BottomUp 방법을 이용하여 문제를 해결하였다.

 

import sys

n = int(sys.stdin.readline())

nums = list(map(int , sys.stdin.readline().split(" ")))

dp =nums.copy()

for i in range(1, n):
    dp[i] = max(dp[i-1]+dp[i],dp[i])
    
print(max(dp))