BoB004-H: Arithmetic Subsequence

2 secs 1024 MB
kyaneko999

解説


の時, 自身が等差数列になるので答えは です.
の時,初項が ,第 項が )であるような部分列を考えます.
この部分列が等差数列になるならば,公差は と一意に定まります.
よって,以下のような操作により,初項が ,第 項が の等差数列であるような部分列のうち長さが最大のものを構成できます.

  • 部分列 から始めて の順に が現在の部分列の末尾よりちょうど 大きければ部分列の末尾に追加する.

それぞれについて の探索を行うことになるので,全体の計算量は となります.

解答例(Python)