プロンプトと設定
末尾が先頭につながっている長さ n の整数配列が与えられたとき、連続する部分配列は端をまたいで折り返す（wrap around）ことができますが、同じ位置を2回使用することはできません。空でない部分配列の最大和を返してください。面接官は応募者に対し、Kadane のアルゴリズムから円形バリアントを導出することや、すべてが負数の配列において total - minSum を単純に使用できない理由を説明するよう求めることがよくあります。
面接官がテストするポイント
- 答えを「折り返しなし」と「折り返しあり」の範囲に分割できるか。
- 配列を複製する代わりに、最大部分配列和と最小部分配列和の補集合を利用できるか。
- すべてが負数の配列、1要素の配列、値が制限された整数入力に対して、空でないという制約を維持できるか。
回答前に確認すべき明確化のための質問
- 部分配列は空でない必要がありますか？ はい。したがって、すべてが負数の入力では最大の負の値が返されます。
- 同じ位置を2回使用できますか？ いいえ。折り返し範囲は、1つの空でない中央範囲の補集合になります。
- 和のみを返しますか、それとも境界（インデックス）も返しますか？ このプロンプトでは和を求めます。境界を返すには、追加のインデックス管理と円形表現が必要です。
30秒の回答フレームワーク
答えを2つのケースに分割します。折り返しなしの範囲は、通常の最大部分配列和です。折り返しありの範囲は、配列全体の合計から空でない最小部分配列和を引いたものと等しくなります。1回の走査で最大和、最小和、および合計和を維持します。最小範囲が配列全体である場合、その補集合は空になるため、代わりに通常の最大値を返します。このアルゴリズムは時間計算量 O(n)、追加空間計算量 O(1) です。
ステップごとの詳細解説
1. 2つのケースの導出
Kadane のアルゴリズムは、最適な折り返しなしの範囲を見つけます。折り返しありの範囲は接尾辞と接頭辞で構成され、その補集合は1つの空でない連続した中央範囲となるため、その和は total - minSubarray です。これらの候補の大きい方を取ることで、すべての有効な範囲をカバーできます。
2. Kadane の不変条件の維持
値 x において、通常の状態は現在の位置で終わる最良の和を保持し、最小状態はそこで終わる最小の和を保持します。前回の現在の状態からそれぞれを更新し、その後に全体（グローバル）の極値を更新します。1要素の負の配列が空として扱われないように、グローバルな最大値を負の無限大に、最小値を正の無限大に初期化します。
3. すべてが負数の入力の処理
すべての値が負数の場合、最小部分配列は配列全体となり、total - minSubarray は 0 になります。これは空の範囲を表し、プロンプトの制約に違反します。最良の和が負である場合は、常に通常の最大値を返します。最小範囲が配列全体をカバーしているかどうかを追跡することも有効な実装ですが、符号のチェックの方がシンプルです。
4. コードと計算量
from typing import List
class Solution:
def maxSubarraySumCircular(self, nums: List[int]) -> int:
total = 0
current_max = current_min = 0
best_max = float("-inf")
best_min = float("inf")
for value in nums:
total += value
current_max = max(value, current_max + value)
best_max = max(best_max, current_max)
current_min = min(value, current_min + value)
best_min = min(best_min, current_min)
if best_max < 0:
return int(best_max)
return int(max(best_max, total - best_min))各要素は1回だけ走査されます：時間計算量は O(n)、追加空間計算量は O(1) です。言語のマシン整数型において合計や途中計算の値がオーバーフローする可能性がある場合は、より大きな整数型を使用してください。
5. 反例と検証
[5,-3,5] の折り返しによる答えは 5 + 5 = 10 です。[-3,-2,-3] は 0 ではなく -2 を返さなければなりません。[1,-2,3,-2] の場合、通常の答えは 3 であり、折り返しの候補がこれを超えることはありません。テストケースには、1要素、すべてが正数の入力、円形配列全体に相当する範囲、整数の限界値に近い和も含める必要があります。
質の高い模範解答
「まず、境界をまたぐ範囲とまたがない範囲を分離します。折り返しなしのケースは Kadane の最大値です。折り返しありの範囲は、配列全体の合計から空でない中央の最小範囲を引いたものとなるため、1回の走査で最大と最小の Kadane の状態を維持します。すべての値が負数である場合、最小範囲は配列全体となり、その補集合は空になるため、通常の最大値を返します。これは時間計算量 O(n)、空間計算量 O(1) で動作し、1要素、すべて負数、折り返しを含む正数、整数の境界値のテストを行います。」
よくある間違い
- 複製した配列で通常の Kadane を実行する → 同じ位置が2回使用される可能性がある → ウィンドウを制限するか、補集合のケースを導出する。
- 常に
total - minSumを返す → すべてが負数の入力で空の範囲（0）が生成されてしまう → 最良値が負となる分岐を先に処理する。 - 空の最小範囲を許容してしまう → 補集合の式で空でない制約が失われる → 最小 Kadane を実際の要素から開始する。
- 不変条件を述べずに O(n) と主張する → 境界ケースの網羅性が証明されない → 両方の範囲ケースとすべての状態を定義する。
フォローアップ質問と回答
開始位置と終了位置を返すにはどうすればよいですか？
最大状態と最小状態の両方について境界を記録します。折り返しによる答えは最小範囲の補集合であり、[minEnd+1,n-1] および [0,minStart-1] として表されます。API が2つの線形な区間を返すのか、それとも円形の開始位置と長さを返すのかを定義してください。
空の部分配列が許可される場合、コードはどのように変わりますか？
答えは少なくとも 0 になるため、現在の和は 0 にリセットされる可能性があります。これによりすべてが負数の場合のセマンティクスが変わるため、空を許容する Kadane バリアントを使用する前にプロンプトを確認してください。
動的なストリームに対して、O(1) で答えを更新できますか？
一方の端への追加であれば接頭辞、接尾辞、および要約値を維持できますが、任意の古い要素を削除すると極値が無効になります。セグメント木やブロック単位の要約が必要になる場合があります。更新の方向、クエリの頻度、および近似が許可されるかどうかを確認してください。
部分配列の長さがちょうど k でなければならない場合はどうなりますか？
補集合の長さが制約されるため、補集合の式は適用できなくなります。配列を長さ 2n のシーケンスとして扱い、累積和または deque を使用して長さ k のウィンドウを維持し、ウィンドウの上限を n に設定します。計算量はクエリパターンによって決まります。