最大サブアレイの面接で詰まらないために、問題定義の言語化、ブルートフォースからKadane導出、全負ケースまで実践的に整理。声に出して説明できる台本を確認してください。
最大サブアレイの面接問題で固まってしまう候補者の多くは、アルゴリズムを忘れたから固まるわけではありません。コードを1行も書く前に答えを口に出して説明したことがないから固まるのです。そして、「どう動くかは知っている」と「別の人にその場で明確に説明できる」の間には、面接官を前に座った瞬間に思う以上に大きな差があります。
このガイドでは、問題の入り口を切り出し、ブルートフォースから最適解を導き、標準例をドライランし、ありそうな追加質問にも教科書を暗唱しているように聞こえずに答えるための、短くて再現しやすい台本を用意します。まず一度読んで、それから声に出してください。練習はそれだけです。
コードに触る前に、まず問題を言葉にする
なぜ最初の一文でつまずくのか
最大サブアレイ問題の回答で最もよくあるミスは、アルゴリズムを間違えることではありません。問題定義を丸ごと飛ばして、そのままコードに入ってしまうことです。面接官はこれをすぐに見抜きます。候補者が本当に問題を考えているのではなく、暗記した解法にパターンマッチしているだけだと分かるからです。そしてこれは、答えを脆くします。面接官が制約を1つ変えた瞬間に、候補者は頼れるものを失ってしまうからです。
多くの人が定義し忘れるのは、「連続している（contiguous）」の意味です。連続部分配列とは、元の配列の中で隣り合って並ぶ要素の並びです。要素を飛ばすことも、順序を入れ替えることもできません。出力は、そのような部分配列の中で得られる最大和です。長さ1の部分配列も含まれます。Introduction to Algorithms (CLRS) では、最大サブアレイ問題はこの意味で厳密に定義されており、この定義は非常に重要です。なぜなら、グリーディーな「正の数だけ全部取る」方針を排除し、この問題を面白くしているのがこの条件だからです。
実際にはこう言います
コードに触る前に、60秒でこう切り出せると理想です。
"入力は、正の数と負の数の両方を含みうる整数配列です。出力は、任意の連続部分配列から得られる最大和です。つまり、ある開始インデックスと終了インデックスを選び、その間の要素をすべて足します。1要素だけ選ぶことはできますが、要素を飛ばしたり、配列を回り込んだりはできません。例として [-2, 1, -3, 4, -1, 2, 1, -5, 4] では、答えは [4, -1, 2, 1] から得られる 6 です。まずブルートフォースで、正しいイメージを持てているか確認してから、より効率的な解法を見ます。"
これで十分です。45秒程度で、入力と出力が明確で、具体例があり、しかも記憶の再生ではなく問題を筋道立てて考えるつもりだと伝わります。面接官は、あなたが文字を1つ書く前に、何を解いているのか理解していると分かります。
より良い答えが自然に見えるよう、まずブルートフォースから始める
ブルートフォースは「ダメ」ではなく、橋渡しです
O(n²) の解法は面接対策で悪者扱いされがちです。たいていは、候補者が「本当の答え」に進む前の恥ずかしい下書きだと扱うからです。でも、その見方は間違っています。ブルートフォースが役に立つのは速いからではありません。速いわけではないのは明らかですが、最大サブアレイの和が何を測っているのかを具体化してくれるからです。効率化する前に、何を測ろうとしているのかを明確にしてくれます。
ブルートフォースの発想は単純です。開始位置の候補をすべて試し、そこから1要素ずつ部分配列を伸ばしていき、累積和を追いながらこれまでの最大値を更新します。二重ループで、余計な工夫はありません。外側のループで開始位置を選び、内側のループで終了位置を順に伸ばします。全体の最大値を保持し、最後にそれを返します。
実際にはこう見えます
配列 [-2, 1, -3, 4, -1] を考えます。インデックス0から始めると、部分配列 [-2] は -2、[-2,1] は -1、[-2,1,-3] は -4、[-2,1,-3,4] は 0、[-2,1,-3,4,-1] は -1 です。インデックス1から始めると、[1] は 1、[1,-3] は -2、[1,-3,4] は 2、[1,-3,4,-1] は 1 です。以下同様です。
ここで直感的に分かるのは、同じ開始位置から伸ばしている限り、累積和に1要素を足しているだけだということです。和を毎回ゼロに戻しているわけではなく、そのまま持ち越しています。この観察こそが、効率的解法の核です。
ブルートフォースの中に隠れている漸化式
内側のループが「同じ累積和に足し続けるだけ」だと分かると、もっと鋭い問いが立てられます。外側のループを毎回最初から回し直す必要は本当にあるのでしょうか。累積和が十分に負になって、その後に続く要素の足を引っ張るなら、その和は捨てて、現在の要素からやり直すべきです。逆に、累積和がまだ正なら、そのまま持ち越した方が得です。
この「延長するか、やり直すか」という判断が、Kadane のアルゴリズム の全体像です。厳密には動的計画法の漸化式で、インデックス i で終わる最大部分配列は、i の要素単体か、i-1 で終わる最大部分配列に i の要素を足したもののどちらかです。二重ループを1回の走査に畳み込めるのは、内側ループの状態を再計算せずに持ち越せると分かったからです。
面接官が聞きたい Kadane の説明を使う
リセット規則が妙に感じるのは、口に出すまでです
Kadane のアルゴリズムを説明するとき、候補者が最もよくつまずくのがリセット規則です。「和が負になったらリセットします」と言うことが多いのですが、これは近いようで少し違います。経験豊富な面接官なら、そこをすぐ突っ込んできます。より正確に言うなら、累積和が負になった時点で、それを次の要素に持ち越すと、その要素の寄与はゼロから始めるより悪くなります。負のプレフィックスは、必ず悪影響を与えます。現在の要素からやり直す方が、負の和を引きずるより常に同等以上に良いのです。
これは小手先のテクニックでも、経験則でもありません。漸化式の帰結です。`current_max = max(nums[i], current_max + nums[i])` という式を見れば分かります。`current_max` が負なら、`current_max + nums[i]` より `nums[i]` 単体の方が大きいので、`nums[i]` だけを採用します。リセットは単に数学です。
実際にはこう見えます
面接前に口に出すための、覚えやすい説明はこちらです。
"変数は2つ持ちます。current_sum は現在のインデックスで終わる最大部分配列の和、best_sum はこれまで全体で見た最大値です。各インデックスで、今の部分配列を延長するのが得か、それともこの要素からやり直すのが得かを判定します。つまり、現在の要素単体と current_sum に現在の要素を足したものの最大を取るだけです。current_sum を更新したら、それが best_sum より大きいかを確認して更新します。1回の走査、定数空間、O(n) 時間です。"
これで十分です。正確で、変数名も出していて、判断の理由も説明しており、しかも手順を暗記している感じがしません。各ステップでの判断を説明しているからです。
良い回答と暗記回答を分ける一文
面接官が、考えて答えているか、暗記で答えているかを見分けるときの決め手は、特定のインデックスで何が起きるかを説明できるかどうかです。「インデックス3では current_sum が負なので、nums[3] にリセットします」は、考えて答えている説明です。「和が負になったらリセットします」はスローガンです。ドライランのときに、各インデックスでの判断を声に出して練習してください。そのナレーションがあると、説明が借り物ではなく、実感のあるものになります。
GeeksforGeeks の Kadane アルゴリズム解説 は、O(n) 時間と O(1) 空間の主張を裏づけており、変数名の慣例を確認するうえでも一読の価値があります。
定番例を、話の流れを見失わずにドライランする
どの面接官も好きな例
配列 [-2, 1, -3, 4, -1, 2, 1, -5, 4] は定番です。複数回のリセット、利益のある延長が続く区間、そして最後にあるものの最適な連続部分配列には含まれない紛らわしい正の要素まで入っているからです。ここで問われているのは、「大きい数を取る」だけのパターンマッチではなく、各ステップの判断を本当に理解しているかどうかです。
正しい答えは 6 で、インデックス3から始まる連続部分配列 [4, -1, 2, 1] から得られます。
実際にはこう見えます
インデックスごとに追いかけながら、口に出して説明します。
- Index 0, value -2: current_sum = max(-2, -2) = -2. best_sum = -2.
- Index 1, value 1: current_sum = max(1, -2+1) = max(1, -1) = 1. Reset. best_sum = 1.
- Index 2, value -3: current_sum = max(-3, 1-3) = max(-3, -2) = -2. best_sum = 1.
- Index 3, value 4: current_sum = max(4, -2+4) = max(4, 2) = 4. Reset. best_sum = 4.
- Index 4, value -1: current_sum = max(-1, 4-1) = max(-1, 3) = 3. Extend. best_sum = 4.
- Index 5, value 2: current_sum = max(2, 3+2) = 5. Extend. best_sum = 5.
- Index 6, value 1: current_sum = max(1, 5+1) = 6. Extend. best_sum = 6.
- Index 7, value -5: current_sum = max(-5, 6-5) = 1. Extend. best_sum = 6.
- Index 8, value 4: current_sum = max(4, 1+4) = 5. Extend. best_sum = 6.
最終的な答えは 6 です。教えるべきポイントは、インデックス1と3でのリセット、そして末尾の4が以前に見つけた最大値を上回らないことです。これらの瞬間は明示的に説明してください。ホワイトボードに数字だけ書いて、面接官が追ってくれると期待しないことです。
落とし穴になる前に、追加質問に答えられるようにしておく
全要素が負のケースでは、雑な初期化がすべてを壊します
best_sum を0で初期化すると、[-3, -1, -2] のような全負配列に対して0を返してしまいます。これは誤りです。正しい答えは -1 です。なぜなら、この問題は最大サブアレイ和を求めるものであり、長さ1の部分配列は有効だからです。0 は、この入力のどの連続部分配列からも得られません。
対処法は、best_sum を0ではなく配列の先頭要素で初期化することです。あるいは、負の無限大で初期化しても構いません。これは些細なエッジケースではありません。正の数が多い例に対する解法を暗記しただけではなく、問題の制約を本当に理解しているかを見るための、意図的な確認です。最大サブアレイの面接では、この追加質問はかなりの頻度で出るので、後付けではなく基本回答の一部として扱うべきです。
実際にはこう言えます
以下の追加質問用スクリプトなら、計算量、初期化、リセットの説明をまとめてカバーできます。
"時間計算量は O(n) です。配列を1回だけ走査するからです。空間計算量は O(1) です。入力サイズに関係なく、追跡する変数は2つだけだからです。全負ケースで大事なのは初期化で、best_sum は0ではなく nums[0] から始めます。そうすれば、存在しないゼロではなく、最も負の少ない要素を必ず返せます。リセット規則自体は同じで、current_sum が次の要素を引きずり下げるならリセットします。ただし全負配列では、ほぼ毎回リセットすることになり、それが正しい挙動です。"
この答えで、3つの追加質問に同時に答えられます。全負の質問をする面接官は、初期化を正しくしたかを見ています。ここをきれいに答えられれば、解法をただコピーしたのではなく、自分で考えていることが伝わります。
境界を返すのは、新しい問題ではなく小さな変更です
面接官が和ではなく実際の部分配列を返すよう求めたとき、候補者は慌てて別解を探しがちです。でも、その必要はありません。同じ O(n) のロジックを使い、追加で3つの変数を追跡すればよいだけです。つまり、start（現在の部分配列の候補開始位置）、end（現在の候補終了位置）、best_start（これまで見つけた最良部分配列の確定開始位置）です。
current_sum を nums[i] にリセットしたら、start を i に更新します。best_sum を更新したら、best_start = start、end = i を記録します。最後に nums[best_start:end+1] を返せばよいです。アルゴリズム自体は変わりません。状態管理が変数3つと代入数行増えるだけです。面接官には、そのように正確に伝えてください。「これは同じアルゴリズムに少しだけ帳簿管理を足したものです。現在の窓の開始位置を追跡し、新しい最大値を見つけたら確定した境界を更新します」と言えば十分です。
CLRS 第4章 では最大サブアレイ問題が詳しく扱われており、技術面接で出典を示したいときの計算量解析の権威ある参考文献です。
答えを、大きな派生問題のテンプレートとして使う
面接官が本題ではなく派生問題を聞いてくる理由
Kadane の説明をきれいに終えると、面接官の中には派生問題に話を移す人がいます。ひっかけるためではなく、表面の解法だけでなく、背後の構造を理解しているかを見るためです。もっともよくある派生は、円環状の最大サブアレイ和です。つまり、配列が末尾から先頭に回り込む場合、最大サブアレイ和はどうなるか、という問題です。
実際にはこう見えます
円環版は、Kadane のアルゴリズムを2回使うときれいに解けます。円環配列での最大サブアレイ和は、次のどちらかです。
- 通常の最大サブアレイ和（答えが回り込まない場合）
- 配列全体の和から最小サブアレイ和を引いたもの（答えが回り込む場合。つまり、真ん中の最小部分を除外する）
まず通常の Kadane を前向きに回して最大値を求めます。次に、比較を逆にした最小サブアレイ版の Kadane を回して最小値を求めます。それを全体和から引き、2つの結果の大きい方を採用します。1つ注意点があります。すべての要素が負なら、2番目の選択肢は0（全体和から全体和を引く）になってしまうので、その場合は1番目を返します。
面接官に伝えるべきポイントはこうです。「円環版も同じ O(n) のロジックを再利用しています。新しいアルゴリズムに飛びつくのではなく、同じ判断構造を目的を変えて2回使っているだけです。」この言い方なら、Kadane を暗記した答えではなく、パターンとして理解していることが伝わります。円環版の詳しい扱いについては、LeetCode 問題 918 に標準的な問題文と参考になるコミュニティ解答があります。
Verve AI が、最大サブアレイの面接対策をどう助けるか
このガイドが解決しようとしている構造的な問題、つまりアルゴリズムは分かっているのに、実戦の圧力で説明が崩れてしまう問題は、読書だけではなく、フィードバック付きの反復練習でしか直りません。一度読んだだけの台本は、面接官に「そのリセットはなぜ正しいのですか？」と聞かれた瞬間に崩れます。説明を声に出して、自分の声を聞き、実際の面接官が返してくるであろう反応に近いフィードバックを受ける必要があります。
Verve AI Interview Copilot は、まさにこの差を埋めるために作られています。あなたが実際に口にした説明を リアルタイムで聞き ます。用意済みの答えではなく、実際に話した内容に反応し、言い足りなかった部分や、うまくつながらなかった部分も拾ってくれます。「和が負になったらリセットします」とだけ言って初期化の話を飛ばしたなら、実際の面接官と同じように Verve AI Interview Copilot がそこを見逃しません。練習のループはライブ会話であって、選択式クイズではありません。
Verve AI Interview Copilot は、模擬面接 も行えます。問題定義、ブルートフォースの確認、Kadane の導出、ドライラン、追加質問まで、流れ全体を通して練習できます。60秒の冒頭説明を練習し、説明の途中で割り込まれ、そこから立て直す練習もできます。実際に面接で試されているのは、その回復力だからです。作業中は見えない形で動くので、補助輪付きの練習ツールではなく、本物の面接に近い感覚で取り組めます。
FAQ
Q: 最大サブアレイを面接で明確かつ自信を持って説明するにはどうすればいいですか？
コードに触る前に、まず問題定義を言葉にしてください。入力を述べ、「連続している」とは何かを定義し、出力を明示し、期待される答えつきの具体例を1つ挙げます。この45秒の導入で、暗記した解法を唱えているのではなく、問題を考えていることが面接官に伝わります。そのあとで、まずブルートフォースから始めて、効率的な答えへ導くと伝えます。
Q: ブルートフォースから Kadane のアルゴリズムをどう導けばいいですか？
ブルートフォースの内側ループは、固定した開始位置から「同じ累積和に足し続ける」だけです。それが分かれば、「外側ループを毎回最初から回し直す必要があるのか、それとも累積和を持ち越せるのか？」と考えられます。累積和が正なら、そのまま持ち越す方が後続の要素に有利です。負なら、現在の要素からやり直す方が常に良いです。この「延長するか、やり直すか」という判断が、Kadane のアルゴリズムの漸化式そのものです。
Q: なぜ累積和が悪化したらリセットするのですか？
負のプレフィックスは、それ以降のすべての要素の寄与を直接下げるからです。漸化式は `current_sum = max(nums[i], current_sum + nums[i])` です。current_sum が負なら、`current_sum + nums[i]` より `nums[i]` 単体の方が大きいので、数学的にリセットが正しいと分かります。これは経験則ではなく、漸化式の直接の帰結です。
Q: すべての数が負の配列にはどう対応しますか？
best_sum は0ではなく、配列の最初の要素で初期化します。全負配列では、正しい答えは最も負の少ない単一要素であり、どの連続部分配列からも0は得られません。0で初期化すると誤答になります。それ以外のアルゴリズムは同じで、ほぼ毎ステップでリセットするだけです。
Q: 定番例のドライランで迷わず追うにはどうすればいいですか？
current_sum と best_sum の2列を追ってください。各インデックスで漸化式を適用して current_sum を更新し、それが best_sum を上回るか確認します。数字をただ書くだけではなく、「インデックス3で current_sum が負になったので 4 にリセットした」というように、判断を声に出して説明してください。面接官が実際に聞いているのは、そのナレーションです。
Q: 時間計算量と空間計算量、その理由は何と言えばいいですか？
時間計算量は O(n) です。配列をちょうど1回走査するからです。空間計算量は O(1) です。入力サイズに関係なく、追跡するのは current_sum と best_sum の2つだけだからです。なぜそうなるかも重要です。中間の部分配列や補助データ構造を保存していないからです。定数空間なのは、漸化式が前のステップの結果だけを必要とするからです。
Q: 和だけでなく実際の部分配列の境界を返すにはどうしますか？
追加で3つの変数を追跡します。1つは候補開始位置で、リセットするたびに更新します。残り2つは確定した開始位置と終了位置で、新しい best_sum を見つけるたびに更新します。アルゴリズムは O(n)、空間計算量は O(1) のままです。新しいアルゴリズムではなく、同じロジックに少しだけ帳簿管理を足したものだと面接官に伝えてください。
これで台本は手元にあります
最大サブアレイの面接問題のプレッシャーは、アルゴリズムそのものではありません。書き始める直前に、あなたが考えていることを見ている相手に対して筋の通った話をしなければならない、その瞬間です。このガイドは、その瞬間に向けて組み立ててきました。問題を明確に定義する60秒の導入、Kadane のアルゴリズムがなぜ動くのかを示す導出、話の流れを失わずに追えるドライラン、そして初期化・計算量・インデックス追跡を慌てずに説明できる追加質問用の台本が、今のあなたにはあります。
次の面接の前に、60秒の説明を1回だけ声に出して練習してください。10回ではなく1回です。各インデックスでの判断を口にしながら、意図を持って1回通す方が、このページを黙って10回読み返すよりずっと価値があります。
Verve AI
コンテンツ