BOJ1912 연속합

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

1912번: 연속합

 

난이도: 실버2

소요시간:20분

 

inputList[i]가 양수라면 dp[i+1]은 max(dp[i]+inputList[i] , inputList[i])를 하면 된다 이전인덱스의 inputList가 음수였다면 뒤에 것이 맥스 일것이고 양수였다면 앞의 것이 맥스 일것이다.

inputList[i]가 음수라면 무조건 전보다 작아진다. 이전의 dp값과 이번 잇풋값을 합쳐서 양수 이면 더하는게 이후에 이득이다. 그러니 양수일경우 더해주고 음수일경우 인풋값으로 설정하고 뒤에값은 새로 덧셈을 시작한다.

#16:30 실버2
import sys

n=int(sys.stdin.readline())
inputList=list(map(int,sys.stdin.readline().split()))
dp=[-1001]*(n+1)
for i in range(n):
    if inputList[i]>=0:
        dp[i+1]=max(dp[i]+inputList[i],inputList[i])
    else:
        if dp[i]+inputList[i]>0:
            dp[i+1]=dp[i]+inputList[i]
        else:
            dp[i+1]=inputList[i]

print(max(dp))