BOJ 2846 - 오르막길

문제

길의 높이가 순서대로 주어질 때, 연속으로 높이가 증가하는 구간 중 가장 큰 높이 차이를 구하라.

입력

첫째 줄에 N, 둘째 줄에 N개의 높이가 주어진다.

출력

가장 큰 오르막길의 높이 차이를 출력한다.

예제

입력	출력
`6` `1 2 1 3 4 1`	`3`

풀이

배열을 순회하며 연속 증가 구간의 높이 차이를 누적하고, 감소하면 새 구간을 시작한다.

인접한 두 원소에서 증가하면 차이를 누적한다
감소하거나 같으면 현재 누적값을 저장하고 0으로 초기화한다
마지막 구간도 저장한 뒤, 저장된 값들 중 최댓값을 출력한다

핵심 아이디어: 한 번의 순회로 모든 오르막 구간의 높이 차이를 O(N)에 구할 수 있다.

코드

n = int(input())
li = list(map(int, input().split()))
a = 0
re = []
for i in range(n - 1):
    if li[i] < li[i + 1]:
        a += li[i + 1] - li[i]
    else:
        re.append(a)
        a = 0
re.append(a)
print(max(re))

복잡도

시간: O(N)
공간: O(N)

문제