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::max;
8
9use std::cmp::max;
10use std::ops::Add;
11
12/// 空ではない連続する部分列の総和を管理する。
13#[derive(Clone, Copy, Default, Debug, PartialEq, Eq)]
14pub struct MaxPartialSum<T> {
15    /// 列の総和
16    pub sum: T,
17    /// 列の左端から連続する空でない部分列の総和の最大値
18    pub left_max: T,
19    /// 列の右端から連続する空でない部分列の総和の最大値
20    pub right_max: T,
21    /// 連続する空でない部分列の総和の最大値
22    pub partial_max: T,
23}
24
25impl<T: Copy> MaxPartialSum<T> {
26    /// 値`value`をもつ長さ`1`の列に対応する[`MaxPartialSum`]を生成する。
27    pub fn new(value: T) -> Self {
28        Self {
29            sum: value,
30            left_max: value,
31            right_max: value,
32            partial_max: value,
33        }
34    }
35}
36
37impl<T> Set for MaxPartialSum<T> {}
38
39impl<T: Copy + Ord + Add<Output = T>> BinaryOp for MaxPartialSum<T> {
40    fn op(self, b: Self) -> Self {
41        let a = self;
42        Self {
43            sum: a.sum + b.sum,
44            left_max: a.left_max.max(a.sum + max(b.left_max, b.sum)),
45            right_max: b.right_max.max(b.sum + max(a.right_max, a.sum)),
46            partial_max: max!(a.partial_max, b.partial_max, a.right_max + b.left_max),
47        }
48    }
49}
50
51impl<T> Associative for MaxPartialSum<T> {}
52
53#[cfg(test)]
54mod tests {
55    use crate::iter::collect::CollectVec;
56
57    use super::*;
58    use rand::Rng;
59
60    #[test]
61    fn test() {
62        let mut rng = rand::thread_rng();
63
64        let n = 20;
65        let a = (0..n).map(|_| rng.gen_range(-100..=100)).collect_vec();
66
67        let (ans, _) = crate::algo::max_partial_sum::max_partial_sum(&a).unwrap();
68
69        let res = a
70            .iter()
71            .map(|&x| Some(MaxPartialSum::new(x)))
72            .fold(Option::id(), |x, y| x.op(y))
73            .unwrap();
74
75        assert_eq!(ans, res.partial_max);
76    }
77}
haar_lib/algebra/max_partial_sum.rs

haar_lib/algebra/
max_partial_sum.rs
