この問題はランレングス圧縮のアルゴリズムの一部分ですが、知らなくても解けます。
以下のステップをたどることでこの問題を解くことが出来ます。
ans
)を用意する。初期値を0に設定する。cnt
)を用意する。初期値を に設定する。cnt
を1増やす。ans
)と現在の連続回数( cnt
)を比較する。cnt
の方が大きければ、ans
を cnt
に更新する。そして、 cnt
を にリセットする。※ランレングス圧縮とは
ランレングス圧縮は、ある連続したデータを、そのデータ一つ分と連続した長さで表現することで圧縮するアルゴリズムです。
例えば の場合、 が 個、 が 個、 が 個なので、 のように表されます。
n = int(input()) A = list(map(int,input().split())) ans = 0 cnt = 1 for i in range(1,n): if(A[i-1]==A[i]): cnt += 1 else: ans = max(ans,cnt) cnt = 1 ans = max(ans,cnt) print(ans)
以下のように二重ループを回すことでもこの問題を解くことが出来ます。
for
文を 回回していますが、計算量は です。理由を考えてみてください。
ヒント: break
で for
文を抜けているということは...
#include<bits/stdc++.h> using namespace std; int main(){ int n; cin >> n; vector<int> a(n); for(int i = 0; i < n; i++) cin >> a[i]; int ans = 1; for(int i = 0; i < n; i++){ int cnt = 0; for(int j = i; j < n; j++){ if(a[i] != a[j])break; i = j; cnt++; } ans = max(ans,cnt); } cout << ans << endl; }
ランレングス圧縮を使った解法です。Pythonでは groupby
を使うことで楽に実装することが出来ます。
from itertools import groupby def to_runLength(S: str): #文字列/リストからラングレス圧縮 grouped = groupby(S) res = [] for k, v in grouped: res.append((k, int(len(list(v))))) return res n = int(input()) A = list(map(int,input().split())) cnt = to_runLength(A) ans = 0 for c in cnt: ans = max(ans,c[1]) print(ans)