しゃくとり法
しゃくとり法は、数列中の条件を満たす連続部分列を数え上げるのに用いられる手法の1つ。他にも条件を満たす連続部分列の最大長や最小長を求めるのにも使われる。
しゃくとり法が使える条件として大事なのは ある部分列が条件を満たすとき、その部分列に含まれる任意の部分列も条件を満たすもしくはある部分列が条件を満たすとき、その部分列を含む任意の部分列も条件を満たすということ。これは区間$ [l, r)を考えたときに、$ f(l) :=条件を満たす最大の$ rとするか、$ f(l) :=条件を満たす最小の$ rと考えることに対応する。そして、それぞれにおいて$ fは広義単調増加になっているところが、このアルゴリズムのみそである。
しゃくとり法のたいていのコードは次のようになる。
code:java
int N = a.length;
int r = 0;
int s = 0; // 計算結果。初期値は何らかの単位元にしておく。
int max = 0;
for (int l = 0; l < N; l++) {
// r を1つ進めたときの区間 [l, r) の値を計算する
if ( r < N && /* [l, r+1) が条件を満たすなら */ ) {
s = // [l, r+1) の値
r++;
}
max = Math.max(max, l - r); // 最長長さを記録
if (l == r) r++; // lがrに追いついた場合は次のループに備えてrを1進める。このとき s は単位元になっているはず。
else s == // そうでない場合は、lがインクリメントされる分 s を減らして [l+1, r) の値で更新する
}