[백준/Python(파이썬)] 1912 연속합

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

 

작년 02월 28일에 풀었던 문제 복습

 

점화식 이해를 위한 설명

주어진 수열 : 2 8 -7 4 8

i = 0 

dp[0] = max(dp[-1] + table[0] , table[0]) = max(2, 2) = 2

dp[1] = max(dp[0] + table[1], table[1]) = max(10, 8) = 10

dp[2] = max(dp[1] + table[2], table[2]) = max(3, -7) = 3

dp[3] = max(dp[2] + table[3], table[3]) = max(3, 7) = 7

dp[4] = max(dp[3] + table[4], table[4]) = max(15, 8) = 15

 

[소스코드]

n = int(input())
a = list(map(int, input().split()))
dp = [0 for _ in range(n)]
result = -1001
for i in range(n):
    dp[i] = max(a[i], a[i]+dp[i-1])
    result = max(result, dp[i])
print(result)

github.com/jisun1125/algorithm-problem-solving/blob/main/baekjoon/no_1912.py

jisun1125/algorithm-problem-solving