haar_lib/algo/
max_partial_sum.rs

1//! 最大連続部分和
2use std::ops::Add;
3use std::ops::Range;
4
5/// 空でない連続する部分列の和で最大のものを返す。
6///
7/// **Time complexity** $O(|a|)$
8pub fn max_partial_sum<T>(a: &[T]) -> Option<(T, Range<usize>)>
9where
10    T: Copy + Ord + Add<Output = T>,
11{
12    let mut t = a.first().copied()?;
13    let mut ret = t;
14
15    let mut t_l = 0;
16    let mut l = 0;
17    let mut r = 0;
18
19    for (i, &x) in a.iter().enumerate().skip(1) {
20        if t + x < x {
21            t = x;
22            t_l = i;
23        } else {
24            t = t + x;
25        }
26
27        if ret < t {
28            ret = t;
29            l = t_l;
30            r = i + 1;
31        }
32    }
33
34    Some((ret, l..r))
35}
36
37#[cfg(test)]
38mod tests {
39    use super::*;
40    use rand::Rng;
41
42    #[test]
43    fn test_zero_array() {
44        assert_eq!(max_partial_sum::<i64>(&[]), None);
45    }
46
47    #[test]
48    fn test() {
49        let mut rng = rand::thread_rng();
50
51        let n = 100;
52
53        let a = (0..n)
54            .map(|_| rng.gen_range(-1000..=1000))
55            .collect::<Vec<_>>();
56
57        let mut ans = i64::MIN;
58
59        for i in 0..n {
60            for j in i + 1..=n {
61                ans = ans.max(a[i..j].iter().sum());
62            }
63        }
64
65        let (res, range) = max_partial_sum(&a).unwrap();
66
67        assert_eq!(res, ans);
68        assert_eq!(a[range].iter().sum::<i64>(), ans);
69    }
70
71    #[test]
72    fn test_all_negative() {
73        let mut rng = rand::thread_rng();
74
75        let n = 100;
76
77        let a = (0..n).map(|_| rng.gen_range(-1000..0)).collect::<Vec<_>>();
78
79        let mut ans = i64::MIN;
80
81        for i in 0..n {
82            for j in i + 1..=n {
83                ans = ans.max(a[i..j].iter().sum());
84            }
85        }
86
87        let (res, range) = max_partial_sum(&a).unwrap();
88
89        assert_eq!(res, ans);
90        assert_eq!(a[range].iter().sum::<i64>(), ans);
91    }
92}
haar_lib/algo/max_partial_sum.rs

haar_lib/algo/
max_partial_sum.rs
