수익[백준 4097]

 

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

 

 

연속합의 최대를 찾는 문제이다. 

while True:
    n = int(input())
    if n == 0:  # 테스트 케이스 종료 조건
        break

    arr = []
    for _ in range(n):
        arr.append(int(input()))

    # DP 배열 초기화
    dp = [0] * n
    dp[0] = arr[0]
    max_sum = dp[0]  # 최대 수익

    for idx in range(1, n):
        dp[idx] = max(arr[idx], dp[idx - 1] + arr[idx])
        max_sum = max(max_sum, dp[idx])  # 최대 수익 갱신

    print(max_sum)