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}
と定義します。
1. 最大区間和DP
まずは最大区間和を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の初期値は以下の通りです。
dp_internal_sum[0] = 0
dp_suffix_sum[0] = 0
DPの漸化式は以下の通りです。
dp_internal_sum[i+1] = max(dp_internal_sum[i], dp_suffix_sum[i] + xs[i])
xs[i]
を使うかどうかで場合分け
dp_suffix_sum[i+1] = max(xs[i], dp_suffix_sum[i] + xs[i])
[0, i)
を使うかどうかで場合分け
コードは以下のようになります(Rust)。
fn range_max(xs: &[i64]) -> i64 { let n = xs.len() // dp_internal_sum[i] = [0, i) での最大区間和 let mut dp_internal_sum = vec![0; n + 1]; // dp_suffix_sum[i] = [0, i) での最大 suffix 和 let mut dp_suffix_sum = vec![0; n + 1]; dp_internal_sum[0] = 0; dp_suffix_sum[0] = 0; for i in 0..n { dp_internal_sum[i + 1] = i64::max(dp_internal_sum[i], dp_suffix_sum[i] + xs[i]); dp_suffix_sum[i + 1] = i64::max(xs[i], dp_suffix_sum[i] + xs[i]); } dp_internal_sum[n] }
2. 最大区間和モノイド
以下の4つの情報を元に持つモノイドを考えます。
- 和
- 最大区間和
- 最大 prefix 和
- 最大 suffix 和
モノイドの二項演算は2つの数列を連結させたときの和・最大区間和・最大 prefix 和・最小 prefix 和として定義します
この4つの情報が必要な理由。
欲しい情報は最大区間和です。
2つの数列を連結させたときの最大区間和を計算するには、最大 prefix 和と最大 suffix 和が必要になります
さらに、2つの数列を連結させたときの最大 prefix 和・最大 suffix 和を計算するには和が必要になります
以上から、和・最大区間和・最大 prefix 和・最小 prefix 和が必要となります。
このモノイドは具体的には以下のように定義できます
#[derive(Clone, Debug, PartialEq, Eq)] struct RangeSumMax { prefix_sum_max: i64, internal_sum_max: i64, suffix_sum_max: i64, sum: i64, } impl RangeSumMax { // 長さ1の数列 [x] に対応する情報 fn unit(x: i64) -> RangeSumMax { RangeSumMax { prefix_sum_max: x, internal_sum_max: x, suffix_sum_max: x, sum: x, } } } struct Concat(Infallible); impl Monoid for Concat { type S = RangeSumMax; // 空列 [] に対応する情報 fn identity() -> Self::S { RangeSumMax { prefix_sum_max: 0, internal_sum_max: 0, suffix_sum_max: 0, sum: 0, } } fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S { RangeSumMax { prefix_sum_max: i64::max(a.prefix_sum_max, a.sum + b.prefix_sum_max), internal_sum_max: { *[ a.internal_sum_max, b.internal_sum_max, a.suffix_sum_max + b.prefix_sum_max, ] .iter() .max() .unwrap() }, suffix_sum_max: i64::max(b.suffix_sum_max, b.sum + a.suffix_sum_max), sum: a.sum + b.sum, } } }
モノイドの総積から最大区間和が求まります。
fn range_max(xs: &[i64]) -> i64 { let xs_info = xs .iter() .copied() .map(RangeSumMax::unit) .fold(Concat::identity(), |acc, x| { Concat::binary_operation(&acc, &x) }); xs_info.internal_sum_max; }
やっていることは最大区間和DPとほとんど同じです。
モノイドを定義するのがつらいですが、セグ木にそのまま応用できるメリットがあります。
3. 累積和の累積min
xs
の累積和を cumsum
とします。
つまり
cumsum[0] = 0
cumsum[i] = xs[0] + … + xs[i-1] (0 ≤ i ≤ n)
とします。
区間和は xs[begin] + .. + xs[end-1] = cumsum[end] - cumsum[begin]
と表せます。
つまり、最大区間和は
max { cumsum[end] - cumsum[begin] | 0 ≤ begin ≤ end ≤ n}
で求まります。
ここで、end
を固定して、
max { cumsum[end] - cumsum[begin] | 0 ≤ begin ≤ end} = cumsum[end] - min {cumsum[begin] | 0 ≤ begin ≤ end}
を求めて、各 end
での値で max
を取ればよいです。
min {cumsum[begin] | 0 ≤ begin ≤ end}
の部分が累積和の累積 min です。
コードにすると以下のようになります。
use ac_library::Min; fn range_max(xs: &[i64]) -> i64 { let n = xs.len(); let cumsum = CumSum::new(xs).cumsum; let cumsum_cummin = CumMonoid::<Min<i64>>::new(&cumsum); (0..=n) .map(|end| { // cumsum[end] - min {cumsum[begin] | 0 <= begin <= end} cumsum[end] - cumsum_cummin.prefix_prod(end + 1) }) .max() .unwrap() }
補足: CumSum と CumMonoid の定義
pub mod cumsum { pub struct CumSum { pub cumsum: Vec<i64>, } impl CumSum { /// 計算量: O(|xs|) pub fn new(xs: &[i64]) -> CumSum { let mut cumsum = vec![0; xs.len() + 1]; for i in 1..xs.len() + 1 { cumsum[i] = cumsum[i - 1] + xs[i - 1]; } CumSum { cumsum } } /// 計算量: O(1) pub fn get_interval_sum(&self, begin: usize, end: usize) -> i64 { self.cumsum[end] - self.cumsum[begin] } } } pub mod cum_monoid { use ac_library::Monoid; pub struct CumMonoid<M> where M: Monoid, { prefix_prod: Vec<M::S>, suffix_prod: Vec<M::S>, } impl<M> CumMonoid<M> where M: Monoid, { pub fn new(xs: &[M::S]) -> CumMonoid<M> { let mut prefix_prod = vec![M::identity(); xs.len() + 1]; let mut suffix_prod = vec![M::identity(); xs.len() + 1]; for i in 0..xs.len() { prefix_prod[i + 1] = M::binary_operation(&prefix_prod[i], &xs[i]); } for i in (0..xs.len()).rev() { suffix_prod[i] = M::binary_operation(&xs[i], &suffix_prod[i + 1]); } CumMonoid { prefix_prod, suffix_prod, } } /// [0, i) の総積 (前から累積) pub fn prefix_prod(&self, i: usize) -> M::S { self.prefix_prod[i].clone() } /// [i, n) の総積 (後ろから累積) pub fn suffix_prod(&self, i: usize) -> M::S { self.suffix_prod[i].clone() } /// [0, i), [i + 1, n) の区間で総積を取る pub fn prod_without1(&self, i: usize) -> M::S { M::binary_operation(&self.prefix_prod[i], &self.suffix_prod[i + 1]) } pub fn prod_without_range(&self, l: usize, r: usize) -> M::S { M::binary_operation(&self.prefix_prod[l], &self.suffix_prod[r]) } } }
この解法は ARC174 A の公式解法と同じものです。
また、ABC331 E - Set Meal の主菜全探索と同じ考え方です(今回は end を全探索をして最大化しています)。
4. Kadane’s Algorithm
最大区間和は max {xs[begin] + .. + xs[end-1] | 0 ≤ begin ≤ end ≤ n }
です。
ここで、end
を固定して、
dp[end] = max {xs[begin] + ... + xs[end-1] | 0 ≤ begin ≤ end }
とします。([0,end)
での最大 suffix sum)
dp
の漸化式は以下のようになります。
dp[0] = 0
dp[end+1] = max(dp[end] + xs[end], xs[end])
このとき、最大区間和は max {dp[end] | 0 ≤ end ≤ n}
と求まります。
fn range_max(xs: &[i64]) -> i64 { let n = xs.len(); let mut dp = vec![0; n + 1]; dp[0] = 0; for end in 0..n { dp[end + 1] = i64::max(dp[end] + xs[end], xs[end]); } *dp.iter().max().unwrap() }
このアルゴリズムは Kadane’s Algorithm と呼ばれています。
参考: Kadane's Algorithm | 最大部分配列 問題 - Ark's Blog
おわりに
この記事では、最大区間和を求める方法を4つ紹介しました。
どの方法の考え方も他の問題で使えそうなので、覚えておきたいです。