dp-サブアレイの最大値について
概要
[x0, x1, ..., xn]があるときに、どのindexでサブアレイを切り取ると、最大となるか- 累積和だけで対応できないようなケース
- 最大となるには累積途中のマイナスを含んではならない
- 動作をシミュレーションするために、dpが必要
- カダンのアルゴリズムという名称がついていて一般化することができる
- 累積積も計算することができる
- min, maxを保存するdpになる
0が出現した時、今の値にリセットする処理を入れる
累積和の具体例
def solve(num):
if len(num) == 1:
return num[0]
dp = [-float('inf')]*len(num)
dp[0] = num[0]
for i in range(1, len(num)):
if dp[i-1] >= 0:
dp[i] = num[i] + dp[i-1]
else:
dp[i] = num[i]
return max(dp)
solve(num=[-2,1,-3,4,-1,2,1,-5,4]) == 6
累積和のdpの変数を作らない場合の一般化
def max_subarray(nums):
best_sum = 0
current_sum = 0
for num in nums:
current_sum = max(0, current_sum + num)
best_sum = max(best_sum, current_sum)
return best_sum
累積積の具体例
from dataclasses import dataclass
@dataclass
class MinMax:
min: int
max: int
def solve(nums):
if len(nums) == 1:
return nums[0]
dp = [MinMax(0, 0) for _ in range(len(nums))]
dp[0] = MinMax(nums[0], nums[0])
for i in range(1, len(nums)):
dp[i].max = max(nums[i] * dp[i-1].min, nums[i] * dp[i-1].max, nums[i]) # 前が0のとき、今の値にリセットする
dp[i].min = min(nums[i] * dp[i-1].min, nums[i] * dp[i-1].max, nums[i])
return max([x.min for x in dp] + [x.max for x in dp])
assert solve([2,3,-2,4]) == 6
assert solve([-2,0,-1]) == 0