haar_lib/algebra/
max_partial_sum.rs

1//! 空ではない連続する部分列の総和の最大値
2//!
3//! # Problems
4//! - <https://yukicoder.me/problems/no/776>
5pub use crate::algebra::traits::*;
6
7use crate::{impl_algebra, max};
8
9use std::cmp::max;
10use std::marker::PhantomData;
11use std::ops::Add;
12
13/// 空ではない連続する部分列の総和を管理する。
14#[derive(Clone, Copy, Default, Debug, PartialEq, Eq, Hash)]
15pub struct MaxPartialSum<T> {
16    /// 列の総和
17    pub sum: T,
18    /// 列の左端から連続する空でない部分列の総和の最大値
19    pub left_max: T,
20    /// 列の右端から連続する空でない部分列の総和の最大値
21    pub right_max: T,
22    /// 連続する空でない部分列の総和の最大値
23    pub partial_max: T,
24}
25
26impl<T> MaxPartialSum<T>
27where
28    T: Copy + Ord + Add<Output = T>,
29{
30    /// 値`value`をもつ長さ`1`の列に対応する[`MaxPartialSum`]を生成する。
31    pub fn new(value: T) -> Self {
32        Self {
33            sum: value,
34            left_max: value,
35            right_max: value,
36            partial_max: value,
37        }
38    }
39
40    /// `MaxPartialSum`を合成する。
41    pub fn compose(self, b: Self) -> Self {
42        Self {
43            sum: self.sum + b.sum,
44            left_max: self.left_max.max(self.sum + max(b.left_max, b.sum)),
45            right_max: b.right_max.max(b.sum + max(self.right_max, self.sum)),
46            partial_max: max!(self.partial_max, b.partial_max, self.right_max + b.left_max),
47        }
48    }
49}
50
51/// [`MaxPartialSum`]の合成
52#[derive(Copy, Clone, Debug, Default, PartialEq, Eq, Hash)]
53pub struct Composition<T>(PhantomData<T>);
54impl<T> Composition<T> {
55    /// [`Composition<T>`]を返す。
56    pub fn new() -> Self {
57        Self(PhantomData)
58    }
59}
60
61impl_algebra!({T: Copy + Ord + Add<Output = T>} Composition<T>; set: MaxPartialSum<T>;
62              op: |_, a: Self::Element, b| a.compose(b); assoc;);
63
64#[cfg(test)]
65mod tests {
66    use crate::{algebra::option::AppendId, iter::collect::CollectVec};
67
68    use super::*;
69    use rand::Rng;
70
71    #[test]
72    fn test() {
73        let mut rng = rand::thread_rng();
74
75        let n = 20;
76        let a = std::iter::repeat_with(|| rng.gen_range(-100..=100))
77            .take(n)
78            .collect_vec();
79
80        let (ans, _) = crate::algo::max_partial_sum::max_partial_sum(&a).unwrap();
81
82        let m = AppendId(Composition::new());
83
84        let res = a
85            .iter()
86            .map(|&x| Some(MaxPartialSum::new(x)))
87            .fold(m.id(), |x, y| m.op(x, y))
88            .unwrap();
89
90        assert_eq!(ans, res.partial_max);
91    }
92}
haar_lib/algebra/max_partial_sum.rs

haar_lib/algebra/
max_partial_sum.rs
