연속합 (BOJ-1912)

01 Mar 2021 in ALGORITHM

‘시간제한 1초, 메모리제한 128MB, BOJ-1912’

연속합 (BOJ-1912)
다이나믹 프로그래밍으로 첫번째 요소에서부터 최대 연속합을 기록하는 방법을 이용하면 된다. 점화식을 구하면 다음과 같다

dp[i] = max(dp[i - 1] + li[i], li[i])

우선 첫번째 요소일때의 최대 연속합은 자기 자신이므로 dp[1] = li[0]으로 초기화 해주고 이후부터 점화식을 적용하면 된다.
그리고 기록된 dp들 중에서 최댓값을 출력해주면 된다.

DP를 활용한 풀이

n = int(input())
li = list(map(int, input().split()))

dp = [0] * n
dp[0] = li[0]

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

print(max(dp))