백준 1912
최대가 되는 연속 합 구하기.
- n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.
- 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다.
- 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
입출력
| 입력 | 출력 |
|---|---|
| 10 10 -4 3 1 5 6 -35 12 21 -1 | 33 |
| 10 2 1 -4 3 4 -4 6 5 -5 1 | 14 |
| 5 -1 -2 -3 -4 -5 | -1 |
dp로 푸는 것이라는 걸 알면 매우 쉽지만 문제만 보고 바로 dp를 떠올리지는 못했다.
접근 방식
: i번째 원소와 바로 이전 dp와 i번째 원소의 합을 비교해서 더 큰 수를 dp에 넣는다.
코드
n = int(input())
nums = list(map(int, input().split()))
dp = []
dp.append(nums[0])
for i in range(1, len(nums)):
dp.append(max(nums[i], nums[i]+dp[i-1]))
print(max(dp))
