[Python] 백준 1912번 연속합

문제

1912번: 연속합

입력

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

출력

• 첫째 줄에 답을 출력한다.

입력 예제

10
10 -4 3 1 5 6 -35 12 21 -1

10
2 1 -4 3 4 -4 6 5 -5 1

출력 예제

33

14

문제 풀이

• 연속되는 수의 합 중 가장 큰 값을 구해줘야 하므로 항상 현재 인덱스의 값 + 이전 인덱스의 값과,  현재 인덱스의 값을 비교하여, 더 큰 값을 넣는다.
• 이렇게 되면 작은 수가 나왔을 때 덧셈을 수행하여 현재 인덱스에 넣게되고, 그 다음 인덱스에서 다시 비교를 수행하여 현재 인덱스와 현재 인덱스의 값 + 이전 인덱스의 값을 더한 합을 비교하여 더 큰 수를 넣게되어, 가장 큰 수의 합을 구할 수 있게 된다.
• 따라서 점화식은 아래와 같다.

dp[i] = max(array[i], dp[i - 1] + array[i])

• 이후 dp테이블에서 가장 큰 값을 출력하면 가장 큰 합의 값을 구할 수 있다.

코드

n = int(input())
array = list(map(int,input().split()))
dp = [-1001] * 100001
dp[0] = array[0]
for i in range(len(array)):
    # dp테이블에 array[i], array[i] + dp[i - 1]중 최댓값 넣어주기
    dp[i] = max(array[i], dp[i - 1] + array[i])
print(max(dp))