백준 1912 연속합

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

1912번: 연속합첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.www.acmicpc.net

그냥 평범한 dp

n[i]는 n[i]를 끝값으로 하는 가장 큰 수

%%점화식%%

n[i]={

n[i-1]<=0 -> n[i]

n[i-1]>0 -> n[i]+n[i-1]

}

만약 그전수가 0보다 작다면, 더해봤자 손해이므로 그냥 n[i]반환

0보다 크다면, 그전에수에n[i]를 더한값 반환

배열을 1개만 써도 상관없음

n=int(input())num_list=list(map(int,input().split()))
max_list=[num_list[0]]+[0 for _ in range(n-1)]for i in range(1,n):
    last_cnt=max_list[i-1] #이전의 숫자    if last_cnt<=0:
        max_list[i]=num_list[i]    else:        max_list[i]=num_list[i]+last_cnt
print(max(max_list))

골드찍었다!