백준 1912 파이썬

1912번: 연속합

 

 

접근 방법

연속된 수를 더해서 가장 큰 수를 만드는 경우를 찾아야한다.

주어진 배열의 숫자 중 음수가 있기 때문에 이를 더하더라도 최대 합을 만들 수 있는 경우를 찾아야한다. 

 

아래 메모는 주어진 테스트케이스를 실제로 더해본 과정을 나타낸다.

arr 은 주어진 입력이고, dp 의 각 원소는 연속된 합을 나타낸다.

dp[i] 의 값은 arr 의 첫번째 원소부터 차례로 더해가면서 업데이트 된다. 즉 dp[i] 의 값은 dp[i - 1] + arr[i] 가 되는 셈이다.

중요한 점은 arr[i] 의 값을 더했는데도 dp[i] 의 값이 arr[i] 보다 작으면, 더하지 않고 그냥 arr[i] 를 dp[i] 의 값으로 할당한다.

 

코드

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

dp = [0] * N
dp[0] = arr[0]
for i in range(1, N):
    dp[i] = max(dp[i - 1] + arr[i], arr[i])
print(max(dp))