1. 문제

출처: 백준 1912번 연속합

2. 풀이

문제 풀이의 핵심은 "연속"합이라는 데에 있다.

현재 숫자를 포함해서 쭉 숫자를 앞에서부터 더해온 값과 현재 숫자 하나만을 비교했을 때,
현재 숫자가 크다면 앞에서 더해온 값은 의미가 없다고 볼 수 있다.
총합을 키우는 데 기여할 수 없기 때문이다.

따라서 현재까지의 숫자를 쭉 더해온 값을 DP 방식으로 저장하고, 위의 설명처럼 비교하면 된다.
만약, 현재 숫자가 더 크다면 저장하는 값은 현재 숫자 하나만 하면 된다.

3. 소스코드

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

dp = [0] * n
dp[0] = numbers[0]
for i in range(1,n):
    dp[i] = max(numbers[i],numbers[i]+dp[i-1])
print(max(dp))

4. 그 외

처음에는 영 개념을 못 잡아서, for문을 잔뜩 돌려서 max 값을 찾으려고 했다. 당연히, 시간 초과가 떴었다. 새로운 접근 방식을 보고는 진짜 단순하네라고 생각하면서도, 이런 방식으로 생각할 수 있도록 노력해야겠다고 생각했었다.