最大区間和の求め方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}

と定義します。

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つ紹介しました。

  1. 最大区間和DP
  2. 最大区間和モノイド
  3. 累積和の累積min
  4. Kadane’s Algorithm

どの方法の考え方も他の問題で使えそうなので、覚えておきたいです。

2023年の数学のふりかえり

こんにちは、ぱるまです。この記事では2023年にツイートした数学の話を振り返ってみます

ルベーグ積分の普遍性 (2月)

ツイートが消えたとき用の画像

ルベーグ積分が普遍性で書けるのおもしろいなぁってなりました。

距離空間の三角不等式も順序集合の推移律も(豊穣圏の)射の合成 (2月)

ツイートが消えたとき用の画像

これも alg-d さんの動画を見て知ったことです。おもしろいなぁと思いました。

以下の2つは $\hom(x, y) \times \hom(y,z) \to \hom(x,z)$ (射の合成) の特殊ケースとみなせるようです。(三角不等式の方は $\mathbb{R}_{\geq 0}$ -豊穣圏を考える)

  • $d(x,y) +d(y,z) \leq d(x, z)$ (三角不等式)
  • $x\leq y$ かつ $y \leq z$ ならば $x \leq z$ (推移律)

関数の連続性について動画を出しました (2月)

youtu.be

2021年ごろにツイートした以下の内容を動画化しました。

これ以降、数学ネタは動画化できてないので、よさそうなネタがあれば動画化したいです。

素数が無限個あること」の証明と「集合全体の集まりが集合でないこと」の証明 (2月)

いろいろな人に指摘されましたが、「素数が無限個あること」の証明が微妙すぎます......。結構伸びてしまいましたが、微妙なツイートをしてしまったなぁという気持ちです。

($P_1, \ldots, P_n$ が素数の全体のとき、$P_1 \cdots P_n + 1$ が素数だというのに飛躍があるのと、$P_1,\ldots, P_n$ が素数のときに、$P_1, \ldots P_n + 1$ が素数であると誤解を生む表現をしてしまっている。)

Stateモナドのお絵描き (2月)

随伴(curry, uncurry)考えると State モナドの見通しが良くなるなぁってことに気づいたのですが、今となってはほとんど忘れてしまっています。(必要になったら思い出します)

ツイートはしてないですが、継続モナドは $\mathrm{ev}\colon A\times X^{A} \to X$ のカリー化を考えると見通しが良かったです。

↓当時書いた雑な絵

dim(V + W) + dim(V ∩ W) = dim(V) + dim(W) は基底で包除原理したもの (3月)

ツイートが消えたとき用の画像

これ気づいたときはちょっと感動しました。 dim(V + W) + dim(V ∩ W) = dim(V) + dim(W) に対する直感的な解釈ができて嬉しかったです

代数系の細かいツイートたち (3月)

特にコメントはないので貼るだけ(後で見返す用)

包除原理を指示関数で解釈する (7月)

ツイートが消えたとき用

包除原理の式は指示関数で書いて展開した式だと思うと見通しがよかったです。 これ気づくまでは包除原理の式はぐちゃぐちゃしててややこしいなと思っていたのですが、これ気づいてだいぶ包除原理の式の見通しがよくなって嬉しかったです。

この件については、ブログの記事にしました。

paruma184.hatenablog.com

米田埋込による min, max の分配法則 (9月)

論理の分配法則に帰着できるのがおもしろいです。

この証明の背景には米田埋め込みがあります(明示的に使ってはないですが)

なお、半順序(inf, sup)だと分配法則は成り立つとは限らないです。

ただ、集合の∩, ∪ や gcd, lcm は分配法則が成り立ちます。 (集合の場合は指示関数使うと {0,1} の min, maxの話になって、gcd, lcm は素因数分解したときの指数でmin, max の話になります。)

まとめ

振り返ると代数ぽいツイートが多めの1年でした。

2023年は代数をちょっとだけ勉強しました(土岡先生の講義資料を読むなどしました)。 まだあまり進んでないので引き続き勉強していきたいです。