[백준/BOJ] - 1912번 python 풀이 - DP

---

Key Point

1. 일반적인 dp문제와 같이 규칙을 찾아 점화식으로 나타내면 되는 문제이다.

2. 이 문제는 본인 값 & 이전 값 dp랑 본인값 합한 값 중 max를 dp에 갱신하면 되는 문제이다.

3. 각 dp에는 해당 수까지의 최대의 값이 저장 되어 있다.

---

시간 초과

import sys
mini = -sys.maxsize
input = sys.stdin.readline
n = int(input())
num = list(map(int, input().split()))
dp = [mini] * 100000
for i in range(n): #8
    sum = num[i]
    for j in range(i-1,-1,-1): #0
        sum += num[j]        
        dp[i] = max(sum,dp[i])
print(max(dp))

---

정답

import sys
input = sys.stdin.readline
n = int(input())
num = list(map(int, input().split()))
dp = [0] * n
dp[0] = num[0]

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