AtCoder Grand Contest 013: A - Sorted Arrays

実装面倒そうだなあと思ったがそうでもなかった。

solution

端から貪欲に区間に切っていけばよい。$O(N)$。

implementation

#!/usr/bin/env python3
n = int(input())
a = list(map(int, input().split()))
result = 1
delta = 0
for i in range(1, n):
    if a[i - 1] < a[i]:
        ndelta = +1
    elif a[i - 1] > a[i]:
        ndelta = -1
    else:
        ndelta = 0
    if delta and ndelta and delta != ndelta:
        result += 1
        delta = 0
    elif not delta:
        delta = ndelta
print(result)