C: Together - AtCoder Regular Contest 082
数列a[i]が与えられる。ある数Xを選んで、各a[i]に対して-1, 0, +1のいずれかを加えることで、a[i]=Xとなるiの個数が最大になるようにしたい。最大値を求めよ。
v[n]=(a[i]=nとなるようなiの個数) という配列を作っておきます。すると、v[n-1] + v[n] + v[n + 1]の最大値が求める答えになります。ただし、両端に注意。O(N)。
数列a[i]が与えられる。ある数Xを選んで、各a[i]に対して-1, 0, +1のいずれかを加えることで、a[i]=Xとなるiの個数が最大になるようにしたい。最大値を求めよ。
v[n]=(a[i]=nとなるようなiの個数) という配列を作っておきます。すると、v[n-1] + v[n] + v[n + 1]の最大値が求める答えになります。ただし、両端に注意。O(N)。