연속합 - 백준 #1912, 실버2, 다이나믹 프로그래밍

문제 링크

1912번: 연속합

풀이

# 입력받기
n = int(input())
arr = list(map(int, input().split()))

# 주어진 배열에서 연속합 중 최댓값 반환
def max_continuous_sum(arr):
    dp = [0] * len(arr)
    dp[0] = arr[0]
    max_sum = dp[0]

    for i in range(1, len(arr)):
        dp[i] = max(dp[i-1] + arr[i], arr[i])
        max_sum = max(max_sum, dp[i])
    return max_sum

def solution(arr):
    return max_continuous_sum(arr)

result = solution(arr)
print(result)