面接官が評価するポイント
整数配列が与えられたとき、最大で1つの要素を削除した後の、空でない連続する部分配列の最大和を返します。削除は任意であり、残りの要素は1つの連続した区間から選ばれなければなりません。
制約と境界条件
- 配列は空ではなく、負、ゼロ、または正の値を含む場合があります。
- 結果は空の配列であってはなりません。
- 区間の端点を削除することは、選択した区間からその端点を除外することと同じです。
- 削除位置と2つの部分配列を全列挙するのではなく、1回のスキャンを目指します。
削除を状態として捉える
現在のインデックスで終わり、削除を行わない場合の最善の和 keep と、1回削除を行ってそこで終わる場合の最善の和 drop を保持します。値 x に対し、keep は新規開始するか延長するかを選択し、drop は x を削除するか、すでに削除済みの状態を延長するかを選択します。
結果の状態と中間状態の分離
最適解が削除を行わない場合もあれば、負の値を削除する場合もあるため、答えは両方の状態を確認する必要があります。drop をゼロで初期化すると、空の部分配列や存在しない要素の削除を許容してしまいます。
線形計算量の説明
各値は2つの定数サイズの状態を更新するため、時間計算量は O(n) であり、追加の空間計算量は O(1) です。ここで終わるすべての有効な区間は、削除を行っていないか、またはちょうど1回削除を行っているかのいずれかであるため、状態の定義は網羅的です。
回答前の確認質問
- 「最大1回」には削除なしも含まれますか？ちょうど1回の削除を必須とすると、答えおよび単一要素の境界条件が変わります。
- 結果は空でない必要がありますか？空の出力を許容すると、誤ってゼロが答えになってしまう可能性があります。
- 合計が32ビット整数をオーバーフローする可能性はありますか？これにより、累積変数の型とテスト範囲が決まります。
30秒の回答フレームワーク
「現在のインデックスで終わる2つの状態を保持します。keep は削除なし、drop は1回削除です。x に対し、keep は再開するか延長するかであり、drop は x を削除するか以前の drop を延長するかです。答えは両方の状態で確認された最大値です。すべて負の入力に対応するため、ゼロではなく最初の要素で初期化し、O(n) の時間と O(1) の空間を実現します。」
ステップごとの詳細解説
直前の状態を keepPrev および dropPrev とします。これらを次のように更新します：
keep = max(x, keepPrev + x)
drop = max(dropPrev + x, keepPrev)2行目の keepPrev は現在の要素を削除することを意味し、以前の区間にはすでに要素が含まれています。dropPrev + x は削除が以前に行われ、現在の値が追加されることを意味します。どちらかの状態を上書きする前に、古い値を保存してください。
1要素の配列の場合、keep はその要素であり、drop は正当な空の区間を表してはなりません。drop を負の無限大で初期化して2番目の要素から更新するか、空でないルールを維持しつつ明示的な最初の要素のセマンティクスを定義します。
模範的な高評価の回答
「この問題を2つのDP状態に分割します。keep は削除なしでこのインデックスで終わる最善の和、drop は1回削除した後の最善の和です。各 x に対し、古い状態を使用して keep=max(x, keep+x) と drop=max(drop+x, oldKeep) を計算します。すべて負の配列がゼロを返さないように最初の値から初期化し、両方の状態全体の最大値を取ります。各値の処理は定数時間で行われるため、O(n) の時間と O(1) の空間になります。」
よくあるミス
- 削除の状態を持たずに通常の Kadane のアルゴリズムを実行する。
dropをゼロで初期化し、空の区間を許容してしまう。- 更新済みの
keepからdropを計算し、1つの値を2回使用してしまう。 - 問題の境界条件を確認せずに空の結果を許容してしまう。
- 正の配列のみをテストし、すべて負の場合、1要素の場合、および端点削除のケースを見落とす。
失敗の兆候と修正方法
[-5] に対してゼロを返すのは、空でないルールに違反しています。[1,-2,0,3] が通常の Kadane のアルゴリズムを上回らない場合、削除状態が寄与していません。まず不変条件を書き出し、次に小さな配列で1遷移ずつトレースしてください。
プロダクション実装
入力範囲に対して十分な幅を持つ累積変数を使用します。区間を返すには、各状態とともに開始インデックス、削除インデックス、終了インデックスのメタデータを保持します。状態数は定数のままですが、タイブレークは決定論的である必要があります。
検証チェックリスト
1要素、すべて負、すべて正、途中の負の削除、端点の削除、複数の最適解、最大値のケースをテストします。小さな配列については、任意の削除を全列挙して Kadane を実行する O(n²) の参照実装と比較し、ランダム化差分テストを使用します。
フォローアップの質問と回答
1回の削除が必須の場合は何が変わりますか？
解は drop を使用しなければならないため、単に keep を返すことはできません。1要素の配列には正当な空でない結果が存在しないため、APIには明示的な番兵値または最小の入力長が必要です。
累積和で解くことはできますか？
累積和を用いると、削除位置と区間を O(n²) で全列挙できます。左右からの最大部分配列の前処理を行うことで、O(n) の空間を用いて O(n) を達成できますが、2状態のスキャンの方が空間効率に優れています。
実際の区間を復元するにはどうすればよいですか？
各状態とともに開始インデックスと削除インデックスを保持します。新規開始時に開始位置をリセットし、現在の値を削除するときにインデックスを記録し、最善の答えを出した状態から終了位置をバックトラックします。
評価基準
- 状態定義：削除なしと1回削除を明確に区別しているか。
- 正しい遷移：古い状態を使用し、新規開始、延長、および現在の削除を網羅しているか。
- 完全な境界処理：すべて負、1要素、空でない条件、およびオーバーフローのケースを処理しているか。
- 正確な計算量：O(n) の時間と O(1) の追加空間を達成しているか。
- 強力な検証：参照全列挙実装と境界条件に焦点を当てたテストを提案しているか。
コンプライアンスチェック
状態遷移、空でない境界条件、および計算量の主張が一貫していることを確認してください。
面接回答チェックリスト
2つの不変条件を述べ、両方の遷移を記述し、古い値の保存と最初の要素による初期化を強調し、その後に計算量とランダム化差分テストを提示します。
1行のまとめ
1回の削除を許容することで、Kadane の連続状態DPに「すでに削除済み」という次元が加わり、線形時間と定数空間で空でない最適解が得られます。