[Python/파이썬] 백준 4097번 수익

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

 

코드

from sys import stdin
input = stdin.readline

while True:
    n = int(input())
    if n == 0:
        break
    p = [int(input()) for _ in range(n)]
    ans = 0
    dp = [0]*n
    for i in range(n):
        dp[i] = max(dp[i-1]+p[i], p[i])  # 계속 이어나가기 vs 새로운 시작
    print(max(dp))

 

dp[i]에는 i번째 원소까지 확인했을 때, 마지막 원소(i번째)가 포함된 부분 배열 중 가장 합이 큰 부분 배열의 합이 저장된다. 그러므로 dp[i]에는 계속 이어나갔을 때의 값인 dp[i-1]+p[i]와 i번째 부터 새로 시작했을 때의 값 p[i] 중 더 큰 값을 저장하면 된다.