最大区間和の求め方4通り(DP/モノイド/累積和累積min/Kadane's Algorithm) - ぱるまの日記
↑と同じ内容
ARC174 A - A Multiply で最大区間和を求める問題が出てきました。
コンテスト後、最大区間和を求める方法がいくつかあるのを知りました。 この記事では最大区間和を求める方法を4つ紹介します。
以下、長さ n
の整数配列 xs
の最大区間和を求める問題を考えます。
長さ n
の整数配列 xs
に対して、
xs の最大区間和 := max {xs[begin] + … + xs[end-1] | 0 ≤ begin ≤ end ≤ n}
xs の最大 prefix 和 := max {xs[0] + … + xs[end-1] | 0 ≤ end ≤ n}
xs の最大 suffix 和 := max {xs[begin] + … + xs[n-1] | 0 ≤ begin ≤ n}
と定義します。
まずは最大区間和をDPで直接求める方法を説明します。
最大区間和のDPと最大 suffix 和のDPを以下で定義します
dp_internal_sum[i] = [0, i) における最大区間和
dp_suffix_sum
が必要dp_suffix_sum[i] = [0, i) における最大 suffix 和
(i
の範囲は 0 ≤ i ≤ n
)
DPの初期値は以下の通りです。