Fog dissipation schedule

한 해안 도시에는 N개의 관측 지점이 일렬로 배치되어 있다.

각 지점에는 안개의 농도를 나타내는 정수 Ai가 기록되어 있다.

기상청은 안개를 제거하기 위해 다음 규칙에 따라 작업을 수행한다.

• 한 번의 작업에서 연속한 구간 하나를 선택한다.
• 선택한 구간에 포함된 모든 지점의 안개 농도를 1씩 감소시킨다.
• 농도가 0인 지점은 더 이상 감소시킬 수 없다.

모든 지점의 안개를 완전히 제거하기 위해 필요한 최소 작업 횟수를 구하여라.

첫째 줄에 관측 지점의 개수 N이 주어진다.

둘째 줄에 N개의 정수 A1, A2, ..., AN이 공백으로 구분되어 주어진다.

모든 지점의 안개 농도를 0으로 만들기 위해 필요한 최소 작업 횟수를 출력한다.

• 1 ≤ N ≤ 300,000
• 0 ≤ Ai ≤ 10^9

5
1 3 2 1 2

7
2 2 0 1 3 2 4

4

7

안개 농도는 다음과 같다.

1 3 2 1 2

왼쪽부터 살펴보면,

• 첫 번째 지점에서 농도 1만큼 새로운 제거 작업이 시작된다.
• 두 번째 지점에서는 이전보다 2만큼 더 높은 농도를 가지므로 작업 2개를 추가로 시작해야 한다.
• 세 번째와 네 번째 지점에서는 새로운 작업이 필요하지 않다.
• 다섯 번째 지점에서는 농도가 1 증가했으므로 작업 1개가 추가된다.

따라서 필요한 최소 작업 횟수는

1 + 2 + 1 = 4

이다.

농도 배열은 다음과 같다.

2 2 0 1 3 2 4

새로운 작업이 시작되는 시점은 다음과 같다.

따라서 최소 작업 횟수는

2 + 1 + 2 + 2 = 7

이다.

연속 구간을 1씩 감소시키는 작업은, 농도가 증가하는 지점마다 새로운 작업을 시작해야 한다는 의미와 같다.

i번째 위치에서

Ai > A(i-1)

이라면,

Ai - A(i-1)

개의 새로운 작업이 반드시 필요하다.

반대로 농도가 감소하거나 같다면 기존에 진행 중인 작업을 종료하면 되므로 추가 작업은 필요하지 않다.

따라서 답은

A1 + Σ max(0, Ai - A(i-1))

으로 계산할 수 있다.

배열을 한 번만 순회하면 되므로 시간 복잡도는

O(N)

이며,

추가 공간은 거의 사용하지 않으므로 공간 복잡도는

O(1)

이다.

import sys

input = sys.stdin.readline

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

answer = 0
prev = 0

for x in A:
    if x > prev:
        answer += x - prev
    prev = x

print(answer)