seg_tree/utils/
max_subarray_sum.rs

1use crate::nodes::Node;
2
3/// Implementation of the solution to the maximum subarray problem. It just implements [`Node`].
4#[derive(Clone, Debug, Default, Eq, PartialEq)]
5pub struct MaxSubArraySum {
6    max_sum: i64,
7    max_prefix_sum: i64,
8    max_suffix_sum: i64,
9    sum: i64,
10}
11
12impl Node for MaxSubArraySum {
13    type Value = i64;
14    fn initialize(value: &Self::Value) -> Self {
15        let v = value.to_owned();
16        Self {
17            max_sum: v,
18            max_prefix_sum: v,
19            max_suffix_sum: v,
20            sum: v,
21        }
22    }
23    fn combine(a: &Self, b: &Self) -> Self {
24        Self {
25            max_sum: a
26                .max_sum
27                .max(b.max_sum)
28                .max(a.max_suffix_sum + b.max_prefix_sum),
29            max_prefix_sum: a.max_prefix_sum.max(a.sum + b.max_prefix_sum),
30            max_suffix_sum: b.max_suffix_sum.max(b.sum + a.max_suffix_sum),
31            sum: a.sum + b.sum,
32        }
33    }
34    fn value(&self) -> &Self::Value {
35        &self.max_sum
36    }
37}
38
39#[cfg(test)]
40mod tests {
41    use rand::{distributions::Uniform, thread_rng, prelude::Distribution};
42
43    use crate::{nodes::Node, utils::MaxSubArraySum};
44
45    const N: usize = 1_000;
46
47    #[test]
48    fn max_sub_array_sum_works() {
49        let random = Uniform::from((i64::MIN / (N as i64))..(i64::MAX / (N as i64)));
50        let mut rng = thread_rng();
51        let nodes: Vec<i64> = random.sample_iter(&mut rng).take(N).collect();
52        // See https://en.wikipedia.org/wiki/Maximum_subarray_problem#Kadane's_algorithm
53        let expected_answer = {
54            let mut best_sum = 0;
55            let mut current_sum = 0;
56            for val in &nodes {
57                current_sum = 0.max(current_sum + val);
58                best_sum = best_sum.max(current_sum);
59            }
60            best_sum
61        };
62        let nodes: Vec<MaxSubArraySum> = nodes
63            .into_iter()
64            .map(|x| MaxSubArraySum::initialize(&x))
65            .collect();
66        let result = nodes
67            .iter()
68            .fold(MaxSubArraySum::initialize(&0), |acc, new| {
69                MaxSubArraySum::combine(&acc, new)
70            });
71        assert_eq!(result.value(), &expected_answer);
72    }
73}
seg_tree/utils/max_subarray_sum.rs

seg_tree/utils/
max_subarray_sum.rs
