문제
1912번: 연속합
첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
www.acmicpc.net
풀이
적분으로 생각하면 좀 더 쉽게 접근 가능하다.
회색이 입력으로 주어지는 값들의 그래프, 노란색이 적분 그래프, 주황색이 dp 그래프이다. 구간합은 적분그래프에서 F(x) - F(x-1) 와 같기 때문에 F(x)가 0 이하인 시점부터는 구간합을 적분값이 아닌 원래 그래프 값 f(x)로 정해주면 된다. 그림이 살짝 잘못됐는데, F(x) = 0 이 되는 시점부터 주황색선은 y(x)를 따라가다가 y(x)가 0 이상이 되는 시점부터 다시 합해주면 된다. 코드를 보면 좀 더 이해하기 쉬울 것이다.
N = int(input())
arr = [0] + list(map(int,input().split()))
dp = [0] * (N+1)
dp[1] = arr[1]
max_value = dp[1]
for i in range(2,N+1):
if dp[i-1] <= 0:
dp[i] = arr[i]
else:
dp[i] = dp[i-1] + arr[i]
if max_value < dp[i]:
max_value = dp[i]
print(max_value)'PS > 백준' 카테고리의 다른 글
| 2579번 - 계단 오르기 (0) | 2022.10.21 |
|---|---|
| 1149번 - RGB거리 (0) | 2022.10.21 |
| 17822번 - 원판 돌리기 (0) | 2022.10.12 |
| 15686번 - 치킨 배달 (0) | 2022.10.10 |
| 23291번 - 어항 정리 (0) | 2022.10.01 |