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] = 0dp_suffix_sum[0] = 0
DPの漸化式は以下の通りです。
dp_internal_sum[i+1] = max(dp_internal_sum[i], dp_suffix_sum[i] + xs[i])
dp_suffix_sum[i+1] = max(xs[i], dp_suffix_sum[i] + xs[i])
コードは以下のようになります（Rust）。
fn range_max(xs: &[i64]) -> i64 {
let n = xs.len()
let mut dp_internal_sum = vec![0; n + 1];
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 {
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] = 0cumsum[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] - 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] = 0dp[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つ紹介しました。
- 最大区間和DP
- 最大区間和モノイド
- 累積和の累積min
- Kadane’s Algorithm
どの方法の考え方も他の問題で使えそうなので、覚えておきたいです。
