最大部分配列と最大積部分配列
最大和部分配列にKadaneのアルゴリズムを適用し、最大値と最小値の両方を追跡して積の派生問題に拡張します。
「最大部分配列と最大積部分配列」はCoddyKit上の無料DSA Interview Prepレッスンです。 これはレッスン2/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはDSA Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 DSA Interview Prepコースには全4レッスンが含まれています。
最大和部分配列問題
最大部分配列問題では、数値の1次元配列の中から、合計が最大になる連続部分配列を見つけます。たとえば、[-2, 1, -3, 4, -1, 2, 1, -5, 4]では、部分配列 [4, -1, 2, 1] の合計が最大の 6 になります。総当たりで O(n²) の計算量をかけてすべての部分配列を調べる方法もありますが、Kadane法なら O(n) で解決できます。
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
# Brute force: O(n^2)
max_sum = float('-inf')
for i in range(len(nums)):
curr = 0
for j in range(i, len(nums)):
curr += nums[j]
max_sum = max(max_sum, curr)
print(max_sum) # 6Kadane法の直感
Kadane法では、配列を1回走査しながら、累積値 current_sum を管理します。各要素で、既存の部分配列を延長するか、この要素から新しく始めるかを選択します。current_sum が負になると、その後のどの部分配列にとっても不利になるため、そこから再開します。漸化式は current_sum = max(num, current_sum + num) です。
def max_subarray(nums):
max_sum = current_sum = nums[0]
for num in nums[1:]:
# Extend or start fresh?
current_sum = max(num, current_sum + num)
max_sum = max(max_sum, current_sum)
return max_sum
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray(nums)) # 6Kadane法をトレースする
[-2, 1, -3, 4, -1, 2, 1, -5, 4]に対するKadane法の処理を追ってみます。最初は curr=-2、max=-2 です。1 では、curr=max(1,-2+1)=1、max=1 になります。-3 では、curr=max(-3,1-3)=-2、max=1 です。4 では、curr=max(4,-2+4)=4、max=4 になります。-1 では、curr=3、max=4 です。2 では、curr=5、max=5 です。1 では、curr=6、max=6 です。-5 では、curr=1 になります。4 では、curr=5、max=6 です。このアルゴリズムにより、インデックス 6 で終わる部分配列が最適だと正しく特定できます。
def max_subarray_trace(nums):
curr = max_sum = nums[0]
for i, num in enumerate(nums[1:], 1):
new_curr = max(num, curr + num)
max_sum = max(max_sum, new_curr)
print(f'i={i}, num={num}, curr: {curr}->{new_curr}, max={max_sum}')
curr = new_curr
return max_sum
max_subarray_trace([-2, 1, -3, 4, -1, 2, 1, -5, 4])実際の部分配列を返す
面接官から合計だけでなく部分配列そのものを返すよう求められた場合は、開始インデックスと終了インデックスを追跡する必要があります。num > current_sum + num を満たして再開するときに、temp_start を更新します。max_sum を更新するときは、temp_start を start として保存し、現在のインデックスを end として保存します。これにより、同じ O(n) のアルゴリズムに O(1) のオーバーヘッドが加わります。
def max_subarray_indices(nums):
max_sum = curr = nums[0]
start = end = temp_start = 0
for i in range(1, len(nums)):
if nums[i] > curr + nums[i]:
curr = nums[i]
temp_start = i
else:
curr += nums[i]
if curr > max_sum:
max_sum = curr
start, end = temp_start, i
return max_sum, nums[start:end+1]
print(max_subarray_indices([-2, 1, -3, 4, -1, 2, 1, -5, 4]))
# (6, [4, -1, 2, 1])最大積部分配列問題
最大積部分配列問題は、負の数があるため、最大和の問題よりも複雑です。負の数を2つ掛けると正の数になるため、非常に小さい負の積が、別の負の数を掛けることで最大値になる場合があります。[2, 3, -2, 4]の答えは 6（[2, 3]）です。[-2, 0, -1]の答えは 0 です。各ステップで最大積と最小積の両方を追跡する必要があります。
nums = [2, 3, -2, 4]
# [2,3,-2,4]: products [2, 6, -12, -48]
# subarrays: [2]=2, [2,3]=6, [3]=3, etc.
# max is 6 from subarray [2,3]
nums2 = [-2, 3, -4]
# [-2]*3*[-4] = 24
# negative*negative=positive!
print('Expected:', 24)最大積と最小積の両方を追跡する
重要なポイントは、各位置での現在の最大積が、num、max_so_far * num、min_so_far * num のいずれかになるということです（最後の候補は、負の数によって最小値が最大値に反転する場合に役立ちます）。最小積についても同様です。同じステップで更新済みの値を使わないように、以前の値を使って 両方の cur_max と cur_min を同時に更新します。
def max_product(nums):
max_prod = min_prod = result = nums[0]
for num in nums[1:]:
# All three candidates for new max
candidates = (num, max_prod * num, min_prod * num)
max_prod, min_prod = max(candidates), min(candidates)
result = max(result, max_prod)
return result
print(max_product([2, 3, -2, 4])) # 6
print(max_product([-2, 3, -4])) # 24
print(max_product([-2, 0, -1])) # 0
print(max_product([-2])) # -2min_prod が重要な理由
[-3, -10, 5]を考えてみましょう。-3 の処理後は、max=-3、min=-3 です。-10 の処理後は、候補が (-10, 30, 30) → max=30、min=-10 になります。5 の処理後は、候補が (5, 150, -50) → max=150 です。min_prod を追跡しなければ、大きな負の最小値に別の負の数を掛けたときに起こる反転を見逃してしまいます。古い値を読み取るバグを避けるため、必ず同じ以前の値から max と min の両方を計算してください。
def max_product_traced(nums):
max_p = min_p = result = nums[0]
for num in nums[1:]:
prev_max, prev_min = max_p, min_p
max_p = max(num, prev_max * num, prev_min * num)
min_p = min(num, prev_max * num, prev_min * num)
result = max(result, max_p)
print(f'num={num}: max_p={max_p}, min_p={min_p}')
return result
max_product_traced([-3, -10, 5])
# max_p after -10: 30 (flip!)
# max_p after 5: 150ゼロで積をリセットする
配列内のゼロは、両方の累積積をゼロにリセットし、配列を独立した部分配列に分割する効果があります。num = 0 のとき、max_prod * 0 = 0 と min_prod * 0 = 0 なので、3つの候補はすべて 0 になり、以前の結果の最大値は保持されます。特別な場合分けは必要ありません。一般的な式がゼロを自然に処理します。
def max_product(nums):
max_p = min_p = result = nums[0]
for num in nums[1:]:
cands = (num, max_p * num, min_p * num)
max_p, min_p = max(cands), min(cands)
result = max(result, max_p)
return result
# Zero splits array into independent subarrays
print(max_product([3, -1, 4, 0, 2, 5, -1])) # 10 (2*5)
print(max_product([0, 2])) # 2
print(max_product([-1, 0, -2])) # 0代替案：左から右、右から左への積の走査
別の方法として、左から右、続いて右から左に走査し、ゼロに遭遇したら累積積を 1 にリセットします。最大積部分配列がゼロをまたぐことはないため、一方向で負の数によって結果が悪化しても、逆方向の走査でその反転を捉えられます。この方法は洗練されていますが、面接では最小値・最大値の追跡を使う方法のほうが一般的に期待されます。
def max_product_sweep(nums):
result = max(nums)
left = right = 1
n = len(nums)
for i in range(n):
left *= nums[i]
right *= nums[n - 1 - i]
result = max(result, left, right)
if left == 0: left = 1
if right == 0: right = 1
return result
print(max_product_sweep([2, 3, -2, 4])) # 6
print(max_product_sweep([-2, 3, -4])) # 24
print(max_product_sweep([-2, 0, -1])) # 0Kadane法と積の比較：主な違い
和の部分配列と積の部分配列には、重要な違いがあります。和の場合、負の数は常に不利になるため、貪欲に新しく始めます。積の場合、負の数が2つあると有利になるため、両方の極値を追跡する必要があります。また、ゼロは積にとって終端になりますが、和にとってはそれほど大きな悪影響ではありません。面接で説明するときは、これらの違いを明確に認め、コードを書く前に最小値の追跡が必要な理由を説明してください。
# Max Sum Subarray: O(n) time, O(1) space
def max_sum(nums):
curr = result = nums[0]
for n in nums[1:]:
curr = max(n, curr + n) # restart or extend
result = max(result, curr)
return result
# Max Product Subarray: O(n) time, O(1) space
def max_prod(nums):
lo = hi = result = nums[0]
for n in nums[1:]:
lo, hi = min(n, lo*n, hi*n), max(n, lo*n, hi*n)
result = max(result, hi)
return result
print(max_sum([-2, 1, -3, 4, -1, 2, 1])) # 6
print(max_prod([-2, 3, -4])) # 24計算量と面接のヒント
Kadane法（最大和）も最小値・最大値の追跡（最大積）も、時間計算量 O(n)、空間計算量 O(1)で動作します。面接での重要なヒントは次のとおりです。(1) 最大和では、知識の幅を示すために分割統治法による O(n log n) の代替手法にも触れてください。(2) 最大積では、古いデータを使わないように、以前の値から min_prod と max_prod を同時に更新することを強調してください。(3) 配列を空にできるか、部分配列を空でないものにする必要があるかを必ず確認してください（慣例上、空でない必要があります）。
# Both run O(n) time, O(1) space
# Kadane handles: all negative (returns least negative)
# Product handles: zeros (resets naturally), negatives (tracks both extremes)
nums_all_neg = [-5, -2, -8]
print('Max sum (all neg):', max(max(nums_all_neg[0:1]),
max(x for x in nums_all_neg))) # -2
# Correct: return the maximum element when all are negativeクイックチェック
このレッスンで扱った Data Structures & Algorithms — Coding Interview Prep の概念について、理解度を確認します。
レッスンのまとめ
このレッスンでは、Kadane法により、各要素で延長するか再開するかを選択して最大和部分配列を O(n) で求める方法、負の数による反転が起こるため、最大積部分配列では累積積の最小値と最大値の両方を追跡する必要があること、特別な場合分けをしなくてもゼロによって累積積が自然にリセットされることを学びました。次は、1次元DPテーブルを使って Word Break 問題を扱います。
よくある質問
「最大部分配列と最大積部分配列」レッスンは無料ですか？
はい。「最大部分配列と最大積部分配列」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、DSA Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 DSA Interview Prepコースには全4レッスンが含まれています。
「最大部分配列と最大積部分配列」で何を学びますか？
最大和部分配列にKadaneのアルゴリズムを適用し、最大値と最小値の両方を追跡して積の派生問題に拡張します。 ブラウザで直接実行するハンズオンコードでDSA Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
DSA Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのDSA Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン2/4です。
「最大部分配列と最大積部分配列」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このDSA Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのDSA Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。