制約
$$ |S| = 2 \times10^{5} $$
この問題は尺取法によって範囲をずらすように探索すると$O(|S|)$で解ける.
[l , r )の半開区間で探索すると実装が立ちやすい.
具体的には l をforで回し,その中でwhileで条件を満たす限りrを加算していくことになる.
言葉で表現するより実物を見たほうが理解しやすいと思う.
string s;
cin>>s;
int n = s.size();
int ans = 0;
int r = 0;
for(int l=0;l<n;++l){
r = l;
while(r<n && s[r]=='1'){
++r;
}
ans = max(ans,r-l);
}
cout<<ans<<endl;
rが半開区間になっているかが一目で分かりにくいかもしれないが,whileの条件式を見ればs[r]が0になった瞬間にループが終わるので半開区間で管理していることが理解できる.
以下の例題ではlとr,総和を適切に管理しながら尺取法を実装することによってO(N)で実装できる.