最大部分配列和 (Kadane)｜コードで実践

最大部分配列和 (Kadane)

このレッスンで分かること

Kadane は DP の入門に最適

素朴に全ての部分区間を試すと O(n^3)、累積和を使っても O(n^2) です

配列の中から 連続した部分配列 を選んだとき、その合計が最大になる値を求めましょう

最大部分配列和とは

連続する部分配列の最大和を、Kadane のアルゴリズムで線形時間 O(n) で求めます。本レッスンでは、最大部分配列和の基本から実際の使いどころまでを整理し、現場で迷わず使える形に落とし込みます。

配列の中から 連続した部分配列 を選んだとき、その合計が最大になる値を求めましょう。例えば [-2, 1, -3, 4, -1, 2, 1, -5, 4] であれば、[4, -1, 2, 1] という連続区間の和 6 が最大です。これを 最大部分配列和 (Maximum Subarray Sum) 問題と呼びます。

素朴に全ての部分区間を試すと O(n^3)、累積和を使っても O(n^2) です。しかし Kadane のアルゴリズム を使うと O(n)、つまり線形時間で解けてしまいます。これは現実の場面でも 1 度通り抜けるだけで答えが出る、非常に美しい DP です。

Kadane は「部分配列を伸ばすか、ここで切り直すか」を 1 要素ずつ判断していく オンライン DP。

LIS との違い

前のレッスンで扱った LIS は 部分列 (飛び飛び OK) でしたが、今回は 部分配列 (連続が必須) です。連続が条件になることで、状態が 1 次元のスカラーで済み、計算量が一気に落ちます。

状態の定義

current を「i 番目で 終わる 部分配列の最大和」と定義します。すると、新しい要素 nums[i] が来たとき、選択肢は 2 つです。

これまでの current に nums[i] を足して伸ばす
nums[i] 単独で新しく始める

どちらが大きいかで current を更新し、全体の最大値 best も同時に更新します。式で書くと current = max(nums[i], current + nums[i])、best = max(best, current) です。

Kadane の本質は 「過去を捨てて始め直す」決断。負の累積を抱えて進むより、0 リセットして再出発したほうが得な瞬間がある。

図解

diagram (will load when visible)

Python 実装

Python

def maxSubArray(nums):
    current = nums[0]
    best = nums[0]
    for i in range(1, len(nums)):
        current = max(nums[i], current + nums[i])
        best = max(best, current)
    return best

初期値は nums[0] です。空配列を考慮しない前提なら、これだけで済みます。current と best の 2 変数だけで、空間計算量も O(1) です。

JavaScript 実装

JavaScript

function maxSubArray(nums) {
  let current = nums[0];
  let best = nums[0];
  for (let i = 1; i < nums.length; i++) {
    current = Math.max(nums[i], current + nums[i]);
    best = Math.max(best, current);
  }
  return best;
}

全要素が負の場合

[-3, -1, -2] のように全て負だったらどうなるでしょうか。素朴に「累積が負になったら 0 にリセット」と書くと、空区間 0 を返してしまいます。本問題の制約では 1 要素以上は必ず選ぶ ため、答えは -1 (最大の単独要素) になります。Kadane の current = max(nums[i], current + nums[i]) という形にしておけば、自然と最大の負要素を拾います。

よくある間違い

1 つ目は 空区間を許してしまう。current = max(0, current + nums[i]) と書いてしまうと、全要素負のケースで 0 を返してしまいます。current = max(nums[i], current + nums[i]) が正しい形です。2 つ目は 初期値。best = 0 で始めると、上と同じ理由で誤ります。best = nums[0] から始めましょう。3 つ目は インデックスのループ範囲。i = 0 から始めると current に nums[0] を 2 重に足してしまうので、i = 1 から開始します。

計算量の比較

計算量を整理しておきましょう。素朴な全探索なら O(n^3)、累積和を使った改良で O(n^2)、Kadane なら O(n) 時間・O(1) 空間です。データサイズが大きくなるほど、この差は致命的になります。たとえば n = 10^5 のとき、O(n^2) は 10^10 回の計算を必要としますが、O(n) ならわずか 10^5 回で済みます。手元のマシンで秒オーダーから一瞬への差です。

アルゴリズムの選択は 計算量 で決める。n が大きい問題で O(n^2) を平然と書くのは危険信号。

やってみよう

[5, 4, -1, 7, 8] の最大部分配列和を計算する。答えは 23 (全部足す)。
[-1] の答えは -1。負しかなければ最大の単独要素を返す。
分割統治法 (O(n log n)) でも解けるか考えてみる。範囲をまたぐケースが鍵。
部分配列の 開始と終了のインデックス も返す版を考えてみる。current をリセットした瞬間に開始位置も更新するのがコツ。

Kadane は DP の入門に最適。たった 2 変数で配列を 1 度通すだけ。シンプルさと強さの両立を体感しよう。

よくある質問

Q. この内容は面接でよく聞かれますか？

A. コーディング面接の頻出範囲です。データ構造（リンクリスト・ツリー・グラフ）とアルゴリズム（DP・BFS/DFS）は IT 系大手の選考でほぼ確実に問われます。LeetCode の Top 100 にも該当問題が多数含まれます。

Q. 計算量と空間計算量はどっちを優先しますか？

A. 通常は時間計算量を優先し、空間が制約条件として明示されたら空間も考慮します。例えば「O(1) 空間で」と書かれていれば in-place アルゴリズム必須です。実務では時間 vs メモリのトレードオフを意識しつつ、ボトルネックを実測してから判断します。

Q. 問題が解けないときどう取り組めば良いですか？

A. まず小さな入力（n=3 程度）で手計算し、規則性を見つけます。次にナイーブ解（O(n²) でも可）を書き、最後に最適化します。いきなり最適解を狙うと手が止まりやすいので、段階的に進めるのが定石です。

次のレッスン

次は 隣り合わない最大値 (House Robber) で、隣り合う家を同時に選べない制約のもとで合計金額を最大化する DP を学びます。

事前確認 — 進む前に次の 3 つができることを確認しましょう。

最大部分配列和の要点を自分の言葉で説明できる
このレッスンの最小コード (または操作手順) を見ずに書ける
練習問題やクイズで間違えた箇所を読み直して理解した

理解度チェック (30 秒)

Q. 最大部分配列和とは何か、1 文で説明してください。

この章のポイント

A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。

関連レッスン

最大部分配列和 (Kadane)