連続部分列とは？初心者向けの分かりやすい解説と例題共起語・同意語・対義語も併せて解説！

この記事を書いた人

高岡智則

年齢：33歳性別：男性職業：Webディレクター（兼ライティング・SNS運用担当）居住地：東京都杉並区・永福町の1LDKマンション出身地：神奈川県川崎市身長：176cm 体系：細身〜普通（最近ちょっとお腹が気になる）血液型：A型誕生日：1992年11月20日最終学歴：明治大学・情報コミュニケーション学部卒通勤：京王井の頭線で渋谷まで（通勤20分）家族構成：一人暮らし、実家には両親と2歳下の妹恋愛事情：独身。彼女は2年いない（本人は「忙しいだけ」と言い張る）

はじめに

このページでは連続部分列とは何かを、初心者にも分かるように解説します。連続部分列は、元の並びの中で、隣接する要素をそのまま並べた部分列のことです。「連続」という言葉が大切で、要素の間に別の要素を挟んで飛ばすことはできません。

連続部分列の定義と見分け方

一般的な「部分列」は元の順番を保ちながら取り出しますが、連続部分列は「抽出した要素が元の並びで連続している」ことが条件です。厳密には、配列 A の i から j までの連結部分列を指し、i <= j となる全ての組を含みます。例えば A = [1, 2, 3, 4] なら、連続部分列には [1], [2], [3], [4], [1,2], [2,3], [3,4], [1,2,3], [2,3,4], [1,2,3,4] などが含まれます。

基本の例

身近な例で考えると、整数の列 A = [1, 2, 3, 4] があるとき、連続部分列は上のように複数作ることができます。特に、長さ 1 の連続部分列は [1], [2], [3], [4]、長さ 2 の連続部分列は [1,2], [2,3], [3,4]、長さ 3 の連続部分列は [1,2,3], [2,3,4]、長さ 4 の連続部分列は [1,2,3,4] です。これらはすべて「元の並びの中で隣接する要素だけを取り出したもの」という性質を満たしています。

表で見る連続部分列

head> <th>区間

連続部分列	和	長さ
[1..1]	[1]	1	1
[2..2]	[2]	2	1
[3..3]	[3]	3	1
[4..4]	[4]	4	1
[1..2]	[1,2]	3	2
[2..3]	[2,3]	5	2
[3..4]	[3,4]	7	2
[1..3]	[1,2,3]	6	3
[2..4]	[2,3,4]	9	3
[1..4]	[1,2,3,4]	10	4

この表は、連続部分列の取り方と、対応する和や長さを視覚的に示す一例です。表を見れば、区間を指定すれば必ずその区間に対応する連続部分列が得られることがわかります。なお、実際の問題では「連続部分列の個数を数える」「最大和の連続部分列を求める」など、さまざまな課題が出てきます。

よくある応用例として、最大和の連続部分列問題があります。配列の中から、連続する部分列の和の中で最大のものを見つける問題で、効率的な解法として Kadaneのアルゴリズム が有名です。このアルゴリズムは、左から右へ走査し、現在の和が負になる場合はその区間を打ち切る、という考え方を使います。数学的には「部分和の累積を扱い、負の影響を持つ区間をスキップする」と言い換えることができます。

まとめとポイント

要点は次のとおりです。連続部分列は「隣接している要素だけを取り出した列」です。部分列との違いを意識すると、問題の解き方が変わります。授業やプログラミングの問題で「連続部分列」を扱う機会は多く、上の表や説明を基に、まずは小さな例から理解を深めていくのが良いでしょう。

連続部分列の同意語

連続部分列: 元の列の中で、隣接する要素が連続して並ぶ部分列。例として、a_i, a_{i+1}, ..., a_{i+L-1} のように連続する要素の列を指す。
連続サブシーケンス: 同じく、元の列の中で隣接する要素だけからなる部分列で、英語の consecutive subsequence に相当する表現。
連続部分文字列: 文字列における、連続して並ぶ文字の列。文字列の一部として取り出せる連続部分を指す。
隣接部分列: 隣接して並ぶ要素だけを含む部分列で、連続部分列とほぼ同義として使われることがある表現。
連続要素列: 元の列の中で、隣接する要素をそのままつなげた列のこと。
連続インデックス列: 要素のインデックスが連続して並ぶ部分列の言い換え表現。
区間連続列: 開始位置と終了位置の区間に含まれる、連続した要素の列。
連続ブロック列: 連続して現れる要素のブロックを指す表現。連続部分列の一部として扱われることがある。
連続部分列（文字列特化）: 文字列に対する連続部分列の別称。文字列の連続的な一部を指す。
連続サブストリング: 文字列の連続部分を指す別称として使われる語。