[BOJ] 1912 / 연속합 / Python

[BOJ] 1912 / 연속합 / Python

[BOJ] 1912 / 연속합 / Python

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

1912번: 연속합

 

풀이

연속된 수열 중 가장 큰 합을 갖는 수열의 합을 구하는 문제이다.

 

현재 index 의 값을 더했을때,

 

1. 이전의 값보다 더 큰경우는 더하여 기록하고

2. 더 작을 경우는 '수열의 합의 큰 수' 를 구하기 위해 현 위치에서 새로 수열을 시작한다.

 

N = int(input())

nums = list(map(int, input().split()))
dp = [0] * N
dp[0] = nums[0]
for i in range(1, N):
    dp[i] = max(nums[i], dp[i-1]+nums[i])
    
print(max(dp))

 

간단한 문제여서 그런지 처음 떠올리고 작성한 코드로 한번에 통과하였다.

쉬운 문제였지만, dp 문제에 대해 조금 익숙해지는 느낌이든다.