백준 1912 연속합 - 파이썬

문제.

풀이.

dp[0]에 arr[0]의 값을 넣어준 뒤

연속으로 더하는게 더 큰 숫자면 더한 값을 dp에 넣어주고 더하지 않고 새로운 숫자를 넣어주는게 값이 더 크다면 그 값을 dp에 넣어주는 방식으로 계속 진행을 한다.

그리고 dp에서 제일 큰 값을 출력한다.

 

소스코드.

import sys

n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
dp = [arr[0]]

for i in range(n-1):
    dp.append(max(dp[i] + arr[i+1], arr[i+1]))

print(max(dp))