(파이썬)백준 알고리즘 1912번 연속합

백준 알고리즘 저지 1912번 문제 (https://www.acmicpc.net/problem/1912)

 

 

입력을 담을 origin[]과 큰 수를 저장할 temp[]

현재 입력값과 입력값 + 과거연산값 중 큰걸 선택하여 저장

   ↓

0 10 -4 3 1 5 6 -35 12 21 -1

0  0   0 0 0 0 0    0   0  0   0

↑

origin[i]와 origin[i]+temp[i-1]중 큰 값을 temp[i]에 저장하고

result와 temp[i] 값을 비교하여 최고값 갱신

 

 

 
n=int(input())
origin=[0]
origin+=list(map(int,input().split()))
temp=[0 for _ in range(n+1)]
result=-1001

for i in range(1,n+1):
    temp[i]=max(temp[i-1]+origin[i], origin[i])
    result=max(result,temp[i])
print(result)