문제

풀이

해결방법
lis 알고리즘을 어느정도 응용한듯 한 문제이다. about lis -> lis알고리즘
dp테이블을 1차원 리스트로 잡고
dp테이블 dp[i]는 그 i자리를 마지막으로 더했을 때 의 합의 최솟값을 저장해주고

이는 이런식으로 점화식이 나올 수 있다.

dp[i] = max(array[i], array[i] + dp[i-1])

바텀업 방식으로 dp테이블을 완성해주고
거기서 최댓값을 출력해주면 문제가 해결된다.

코드

# 점화식은 
# dp[i] = max(array[i], array[i] + dp[i-1]
#첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다
import sys

N = int(sys.stdin.readline().rstrip())

dp = [0] * N
array = list(map(int, sys.stdin.readline().split()))

for i in range(N):
  dp[i] = array[i]

#바텀업 방식으로 dp채워주기
for i in range(1, N):
  dp[i] = max(dp[i-1] + array[i], dp[i])

print(max(dp))