[BOJ] 1912번 - 연속합

---

문제설명

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

1912번: 연속합

사고과정

• 연속된 수열을 '몇 개'를 선택했을 때 가장 큰 합을 구하는 것이었다. 그래서 DP 테이블을 어떻게 작성해야 할까 매우 고민했다. 생각보다 너무 복잡하게 생각한 듯 했다..(풀이를 보니..) 주어진 데이터 범위가 최대 10만이였기 때문에 이중 loop만 돌아도 시간초과 에러가 발생할 게 뻔했다. 그래서 한 번의 loop로 해결해야 하는데.. 잘 떠오르지 않았다.
• 풀이를 보니 DP 테이블을 리스트에 수열의 가장 첫번째 원소를 넣어놓고 시작했다. 그리고 수열의 2번째 원소를 탐색하면서, DP 테이블의 값 + 2번째 원소 랑 2번째 원소 값 중 큰 값을 DP 테이블에 append 하는 방식으로 활용했다. 처음에 이렇게 하는 것이 연속된 수열 '몇 개'를 탐색하는 것을 모두 할 수 있을까? 의문을 가져서 연습장에 일일이 하나씩 사례를 들어 살펴보았다. 그려보니 잘되는 걸 확인했다.
• 이유에 대해서 생각하려 해보았는데, 수열의 원소 순서대로 탐색하다가 만약 이전에 구한 합이 작게 되면 그냥 탐색하고 있는 원소 단일 값으로 업데이트 되기 때문이었다. 예를 들어, DP 테이블의 첫번째 원소랑 수열의 2번째 원소의 합이 수열의 2번째 원소 단일 값보다 작게 된다면 그 때는 2번째 원소 값만 DP 테이블에 들어가게 되어서 자동으로 다음부터는 2번째 원소 값으로 시작하는 연속된 수열을 탐색하게 되는 것이다! 
• 생각보다 점화식이 내가 생각했던 것보다 간단하게 되어있어서 아쉬웠다..흑

풀이(스스로 못 푼 풀이)

n = int(input())
array = list(map(int, input().split()))
dp = [array[0]]
for i in range(n-1):
    dp.append(max(dp[i] + array[i+1], array[i+1]))

print(max(dp))