[코테] 백준 다이나믹 프로그래밍 1912번 문제

1912번 : 연속합

문제 링크

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

문제 설명

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

첫째 줄에 답을 출력한다.

문제풀이

1. dp배열을 선언, dp배열에는 연속되는 수열의 합을 저장
2. 입력받은 수열을 처음부터 순회하면서 해당 index의 바로 전까지 연속되는 수열의 합이 음수면 현재값으로 갱신, 양수면 현재값을 더해서 갱신

N = int(input())
arr = list(map(int, input().split()))

dp = [arr[0]] + [0] * (N-1)

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

print(max(dp))