[백준 1912번] 연속합

📖문제:

 

📙풀이:

이전에 연속합 문제를 풀었을 때는 분할 정복 방식으로 최대 부분 합을 작게 쪼개어 풀었으나,

이번에 dp 방식으로 현재 가장 큰 값을 기억(저장?)하는 방식으로 풀어보았다.

그러나, 이 방식으로는 어느 범위에서 연속 합이 가장 큰지는 알 수가 없어, 이러한 문제가 나온다면 다른 방법을 사용해야 할 것 같다.

 

✏️코드:

'''
https://www.acmicpc.net/problem/1912
문제: 연속합
난이도: silver2
'''

index = int(input())
box = list(map(int, input().split()))

# 다이나믹 프로그래밍
curs, maxs = 0, -1000
for i in range(index):
    curs = max(curs, 0) + box[i]
    maxs = max(curs, maxs)

print(maxs)

 

🔗링크:

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