まずは次の問題を考えてみます

(問題X) 以下の条件をともに満たすように、最大でいくつのビルを選べますか

• 選んだビルたちは高さが等しい
• 選んだビルたちは連続している

この問題はビルを先頭から順に見ていくことで \(O(N)\) で解くことができます。

擬似コード

ans=0
height=0
crrent=0
for i in 1..N:
  if height!=H[i]:
    crrent=0
    height=H[i]
  crrent+=1
  ans=max(ans,crrent)
print(ans)

続いて次の問題を考えます

(問題Y) 正整数 \(K\) が与えられます。以下の条件をともに満たすように、最大でいくつのビルを選べますか

• 選んだビルたちは高さが等しい
• 選んだビルたちは \(K\) 個おきに並んでいる

同時に選ぶことができるビルは

• \(1,\ K+1,\ 2K+1,\ 3K+1\ldots\)
• \(2,\ K+2,\ 2K+2,\ 3K+2\ldots\)
• \(3,\ K+3,\ 2K+3,\ 3K+3\ldots\)
• \(\dots\)

という独立な \(K\) 個のグループに分かれます。よってこれらの \(K\) 個のグループそれぞれについて、(問題X)を解けば良いです。
1つのグループについて答えを求めるのに \(O(N/K)\) 時間かかり、それを \(K\) グループ分行うので、全体の計算量は \(O(N)\) になります。

最後にもとの問題を考えます。\(K=1,2,\ldots,\) の全てについて(問題Y)を解くことで \(O(N^2)\) 時間で答えを求めることができます。