sko.kr

アルゴリズム - 0. カダネのアルゴリズム

algorithmsdynamic-programmingarraysoptimizationkadane
By sko•9/27/2025•4 min read

カダネのアルゴリズムを使うタイミング

累積的な性質に基づいて最適な連続部分配列を見つける必要がある時にカダネのアルゴリズムを使用します。最大和に最も一般的に使用されますが、以下のように適応できます：

  • 最大和（古典的な使用例）
  • 最大積（負の数やゼロを扱うための修正を加えて）
  • 特定の性質を持つ最長部分配列（例：和が k に等しい）
  • 最小和（値を否定するか比較を逆にして）
  • 累積状態に基づいて拡張または再開するローカルな決定ができる任意の問題

問題例

株式取引: 日々の株価変動 [-2, 1, -3, 4, -1, 2, 1, -5, 4] が与えられた時、株を保有する最適な連続期間を見つけます。

  • 0 日目: $2 の損失
  • 1 日目: $1 の利益
  • 2 日目: $3 の損失
  • ...以下同様

答え: 3 日目から 6 日目まで保有（部分配列 [4, -1, 2, 1]）で合計$6 の利益。

最も重要な洞察

すべての部分配列はどこかで終わらなければならない - 各位置で最適な局所的決定（拡張 vs 再開）を行うことで、すべての可能な終点とその最適な開始点を確認することで大域的最大値を見つけることが保証されます。

メンタルノート: このアルゴリズムの天才的な点は「インデックス i で終わる最良の部分配列」に焦点を当てていることです。各位置で必要な決定は 1 つだけ：「前のインデックスで終わる最良の部分配列に現在の要素を追加するか、新たに始めるか？」この単純な決定がすべての可能な部分配列を自動的に探索します。

意思決定フレームワーク

各要素で、シンプルな決定に直面します：

  • 現在の部分配列を拡張する（持っているものに追加）
  • 新しい部分配列で再開する（過去を放棄）

コード

function kadanes(nums: number[]) {
  let globalMax = nums[0];
  let localMax = nums[0];

  for (let i = 1; i < nums.length; i++) {
    const currentNum = nums[i];
    // 意思決定フレームワーク
    const extendSubarray = localMax + currentNum;
    const startNewSubarray = currentNum;
    localMax = Math.max(startNewSubarray, extendSubarray);

    globalMax = Math.max(globalMax, localMax);
  }

  return globalMax;
}

疑念を打破

よくある疑念: 「アルゴリズムは各位置で拡張か再開しか考慮しません。現在の部分配列の最初の数要素を削除すれば、より大きな和が得られる場合はどうなりますか？」

これはカダネのアルゴリズムに関する洗練された懸念です。具体例でこれに対処しましょう。

なぜより良い部分配列を見逃すと思ってしまうのか

配列 [-2, 3, 5, -1, 6] を考えてみてください。部分配列を追跡する際、次のように考えるかもしれません：

  • 「位置 4 で、部分配列 [3, 5, -1, 6] の和は 13 です」
  • 「でも [-2, 3, 5, -1, 6] のような部分配列があって、-2 だけを削除したい場合はどうなりますか？」
  • 「アルゴリズムは末尾に追加するか完全に再開するかしかできないようです - 先頭から削除できませんか？」

なぜこの考えが間違っているのか

重要な気づき: すべての可能な「部分的な削除」は、すでに以前の位置で考慮されています！

[-2, 3, 5, -1, 6] をトレースして、カダネがこれをどのように処理するか見てみましょう：

位置 0: localMax = -2  ([-2])
位置 1: localMax = 3   ([3])         → 比較: -2+3=1 vs 3、3を選択 (-2を削除！)
位置 2: localMax = 8   ([3, 5])      → 比較: 3+5=8 vs 5、8を選択
位置 3: localMax = 7   ([3, 5, -1])  → 比較: 8+(-1)=7 vs -1、7を選択
位置 4: localMax = 13  ([3, 5, -1, 6]) → 比較: 7+6=13 vs 6、13を選択

魔法の瞬間: 位置 1 で、1 を得るために拡張する代わりに 3 で再開することを選んだ時、自動的に-2 を削除しました！アルゴリズムはすでに考慮し、最適な選択をしました。

具体例：すべての削除可能性がカバーされている

任意の部分配列を考えてみてください - たとえば、[5, -1, 6]（-2 と 3 の両方を削除）を見逃すことを心配しているとしましょう：

  • 最初の要素[-2]を削除: 位置 1 で再開した時にすでに考慮済み
  • 最初の 2 つの要素[-2, 3]を削除: 位置 2 で再開(5) vs 拡張(8)を比較した時にすでに考慮済み
  • 最初の 3 つの要素[-2, 3, 5]を削除: 位置 3 で再開(-1) vs 拡張(7)を比較した時にすでに考慮済み

位置 4 で終わる部分配列のすべての可能な開始点は、各以前の位置で終わる最良の部分配列を計算した時にすでに評価されています！

なぜ局所的決定がすべてをチェックすることを保証するのか

カダネのアルゴリズムの素晴らしさは、「再開」が単に新しく始めることを意味するだけでなく、次のことを意味することです：

  • 「この点より前のすべてが私の和を悪化させる」
  • 「以前の要素を含むすべての可能な部分配列はすでに評価済み」
  • 「すべてを削除することで、最適な選択をしている」

拡張する時、「最適な開始点からすべてを維持することがまだ有益である」と言っています。再開する時、「すべてを削除する - この点より前で終わる最良の部分配列でさえ事態を悪化させる」と言っています。

保証: すべての部分配列はどこかで終わらなければならず、各可能な終了位置に対して最適な開始を見つけるので、すべての可能な部分配列を暗黙的にチェックしました - 先頭から様々な要素を削除するものすべてを含めて！

← Back to Blog