백준 1912_연속

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

N = int(input())
lst = [0] + list(map(int,input().split()))
dp = [0] * (N + 1)

if max(lst[1:]) < 0:
    ans = max(lst[1:])
else:
    for i in range(1,N+1):
        dp[i] = max(0,dp[i-1] + lst[i])
    ans = max(dp[1:])
print(ans)

• 처음 지점부터 연속합을 더해가며 dp테이블에 기록한다.
• dp 테이블의 해당 지점까지의 연속합의 최댓값이 표기된다.
• 만약 연속합이 -값이면 더이상 연속하지 않아야한다.
• -값인 지점은 0으로 대신 표기한다.