[python] 1912. 연속합

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

 

 

풀이

이번 문제는 연속 합의 최댓값을 구하는 문제입니다.

 

선택을 하냐, 하지 않느냐에 따라 dp[i]가 채워집니다.

 

어려운 문제는 아니였기 때문에 점화식을 구해서 풀 수 있었습니다.

이전 값(dp[i-1])에 이번 값(arr[i])를 더한 값을 0과 비교해서, 최댓값을 dp[i]에 채우도록 풀었습니다. 

 

 

n = int(input())
arr = [0] + list(map(int, input().split()))

dp = [0] * (n+1)

if max(arr[1:]) <= 0: # 모두 음수인 경우
    ans = max(arr[1:]) # 한개만 더한 값이 max
else:
    for i in range(n + 1):
        dp[i] = max(dp[i - 1] + arr[i], 0)
    ans = max(dp)
print(ans)