Namaran

Code daily. Without assist.

2026-09-03

Peak.hs

peak :: [Int] -> Int
peak xs = go 0 (length xs - 1)
  where
    f = (xs !!)
    go lo hi
      | hi - lo < 3 = maximum (map f [lo .. hi])
      | f m1 < f m2 = go (m1 + 1) hi
      | otherwise = go lo m2
      where
        m1 = lo + (hi - lo) `div` 3
        m2 = hi - (hi - lo) `div` 3

main :: IO ()
main = print (peak [1, 9, 2, 3, 4, 5, 6, 7, 3])

これは何を出力するでしょうか?

Answer

7 です。

区間は添字の (0, 8) から始まり、m1 = 2、m2 = 6 です。f 2 は 2、f 6 は 6 で、2 < 6 なので go 3 8 に進み、添字 0 から 2 までが捨てられます。9 は添字 1 にあるので、この時点で候補から外れます。

そのあと (3, 8) では m1 = 4、m2 = 7 で 4 < 7 なので (5, 8) に、(5, 8) では m1 = 6、m2 = 7 で 6 < 7 なので (7, 8) に進みます。幅が3未満になったので、残った [7, 3] の最大値 7 を返します。

f m1 < f m2 だけを見て左の3分の1を捨ててよいのは、値が上がってから下がるだけ、つまり山が1つしかない場合です。そのときは f m1 < f m2 なら頂上が m1 より右にあります。この数列は 1, 9, 2 で一度山を作ってからもう一度上るので前提が成り立たず、最初の比較で本当の最大値を捨ててしまいます。