문제링크

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

예제 1로 설명을 하자면
첫번째 숫자까지의 연속합은 10이 최대,
두번째 숫자까지는 6,
세번째 숫자까지는 9
네번째 숫자까지는 10
이렇게 나아가다가
12 입장에서는 -35를 안고가는것보다
자기 자신부터 시작하는것이 크기 때문에
12부터 다시 시작하게 된다.

이를 DP 테이블을 이용해서 풀어보면

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

이전값+현재값 vs 현재값
을 비교해서 더해나가
최종적으로 DP테이블의 Max값을 출력하면 된다.

풀이

input = __import__('sys').stdin.readline

n = int(input())
numbers = list(map(int, input().split()))

dp = [numbers[0]]+[0]*(n-1)

for i in range(n):
    dp[i] = max(dp[i-1]+numbers[i], numbers[i])
    
print(max(dp))