boj 1912

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

from sys import stdin
from collections import deque

count = int(stdin.readline())
numlist = list(map(int, stdin.readline().split()))
zerocount = 0 ## 입력받는 원소중 0이하의 갯수 만약에 모두다 0이하면 계산을 할 필요없이 무조건 가장큰수를 출력하면 돼 

for i in range(count):
    if numlist[i] <= 0:
        zerocount += 1
if zerocount == count:
    print(max(numlist))
else:
    ans = deque()
    ans.append(numlist[0])
    for i in range(count-1):
        if numlist[i] < 0:
            zerocount += 1
        if numlist[i+1] + ans[i] < 0:
            ans.append(0)
        else:
            ans.append(numlist[i+1] + ans[i])
    print(max(ans))

notion

• 다이나믹 프로그래밍
• 다이나믹 프로그래밍에서 중요한 점 - 기억
• 기억이라고 해서 반드시 뒤로만 전진할 것이 아닌 앞을 보면서 전진하는것이 중요하다!
• 어렵다 다이나믹...