上限以下の最長連続区間

全要素が正の配列A=[2,1,4,2,1]。和が5以下の連続区間の最長長を求める。添字1始まり。 left ← 1; total ← 0; best ← 0 for right = 1 to 5 total ← total + A[right] while total > 5 total ← total − A[left] left ← left + 1 endwhile length ← right−left+1 if length > best best ← length endif endfor 終了時の(best,left,total)はどれか。

答え・解き方を読む

(2,4,3)

図で見る

連続区間の両端を動かす

図を拡大して見る ↗

右端を延ばすと新しい要素を加え、左端を進めると外れた要素を引きます。累積和なら区間末尾までの和から区間直前までを引きます。図の要素数と端位置は操作の例です。

図は問題の関係を整理する模式図です。記号には各問題の数値を当てはめます。寸法・面積・時間の縮尺や、実施工の全条件は表していません。

考える順序

1. 1right=3で総和7から2を除き区間[2,3]の和5
2. 2right=4では1と4を順に除き区間[4,4]の和2
3. 3right=5で[4,5]の和3、最長長は2のまま

選択肢ごとの理由

• 比較 · (3,3,7)

  和が5を超える区間はwhileで縮小されます。

• 比較 · (2,3,5)

  right=4の段階で4も除く必要があります。

• 比較 · (1,5,1)

  要素を必要以上に除く処理ではありません。

• 正解 · (2,4,3)

  right=3で総和7から2を除き区間[2,3]の和5。right=4では1と4を順に除き区間[4,4]の和2。right=5で[4,5]の和3、最長長は2のまま。