連続達成回数を求める擬似言語を、一行ずつ追跡する

1. 変数の役割を決めてから、処理全体を読む

currentとbestは似ていますが、更新条件が異なります。currentは未達成の日を読むと0に戻ります。bestは過去の最長記録なので、その後に未達成の日が来ても減らしません。この意味を先に書くと、「どちらも毎日リセットする」といった誤りを見つけやすくなります。

i ← 1 current ← 0 best ← 0 while (i ≦ n) if (a[i] ≧ target) current ← current + 1 else current ← 0 endif if (current > best) best ← current endif i ← i + 1 endwhile return best

最大値の更新は、達成判定でcurrentを変更した後に行います。比較がcurrent > bestでもcurrent ≧ bestでも、bestの数値だけを返すこの処理では結果は同じです。ただし、最長区間の開始日も記録する拡張では、同点時に更新するかが「最初の区間」「最後の区間」の違いになります。

2. 一回の反復で変わる値を、実行順どおり記録する

初期値はi＝1、current＝0、best＝0です。1日目の12は未達成なのでcurrentは0のままです。2日目の18は「以上」に含まれるのでcurrentが1、bestも1になります。3日目も18なのでcurrentが2、bestが2へ進みます。比較対象の18を除外してしまうと、この途中経過が変わります。

4日目の9ではcurrentだけを0へ戻します。bestは2を保ちます。5日目の20から新しい連続区間が始まり、6日目の21で再び長さ2になります。下表のiは、その行で参照した添字です。本体の最後ではiが1増えるため、最終行の終了時点ではi＝7になります。

3. 反復の前後で成り立つ性質を使って、更新順を検算する

i番目を処理した直後、currentは「i番目で終わる連続達成区間の長さ」、bestは「1番目からi番目までの最長連続達成区間の長さ」です。達成なら昨日の連続区間に1を足し、未達成ならその日で区間が切れるため0にする、と考えればcurrentの更新を説明できます。

新たな最長記録が生まれる可能性があるのは、今回のcurrentが以前のbestを超える場合だけです。従ってcurrent更新後に最大値を比較すれば、同じ性質が次の反復でも保たれます。表を埋めるだけでなく、この説明ができると、配列が600要素になっても手順の正しさを考えられます。

4. 最初・最後・要素0件を、小さな入力で試す

空配列ならn＝0なので、最初の条件1≦0は偽です。a[1]は参照されず、初期値best＝0が返ります。1要素の{18}なら1回だけ実行して1、{17}なら0です。値がしきい値と等しいケースを含めると、≧を誤って>にした実装を検出できます。

末尾の取りこぼしには{4, 18, 19, 20}を使います。正解は3です。条件をi < nにするとi＝4を処理せず2を返します。一方、元の6要素では最後を飛ばしても前半の最長2が残るので、戻り値だけでは誤りが見えません。通常例が通ったことと、境界が正しいことを分けて検証する必要があります。

5. 計算量と仕様変更の影響を説明する

各要素を一度だけ読み、反復の中では一定個数の比較・加算・代入を行います。従って時間計算量はO(n)、入力配列を除く追加領域はi、current、bestなどの一定個数なのでO(1)です。二つのifがあることを、二重ループと混同しないでください。

もし「最長の区間が何日目から始まったか」まで返したいなら、bestを更新した時点の開始添字i−current＋1を記録できます。例えば3日目なら3−2＋1＝2です。同点で更新しない現在の>を使えば、最後の区間ではなく最初に見つかった最長区間を保てます。返す値が増えたら、同点時や空配列の仕様も追加してから変更します。