1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

use crate::nodes::Node;

/// Implementation of the solution to the maximum subarray problem. It just implements [Node].
#[derive(Clone, Debug, Default, Eq, PartialEq)]
pub struct MaxSubArraySum {
    max_sum: i64,
    max_prefix_sum: i64,
    max_suffix_sum: i64,
    sum: i64,
}

impl Node for MaxSubArraySum {
    type Value = i64;
    fn initialize(value: &Self::Value) -> Self {
        let v = value.to_owned();
        MaxSubArraySum {
            max_sum: v,
            max_prefix_sum: v,
            max_suffix_sum: v,
            sum: v,
        }
    }
    fn combine(a: &Self, b: &Self) -> Self {
        MaxSubArraySum {
            max_sum: a
                .max_sum
                .max(b.max_sum)
                .max(a.max_suffix_sum + b.max_prefix_sum),
            max_prefix_sum: a.max_prefix_sum.max(a.sum + b.max_prefix_sum),
            max_suffix_sum: b.max_suffix_sum.max(b.sum + a.max_suffix_sum),
            sum: a.sum + b.sum,
        }
    }
    fn value(&self) -> &Self::Value {
        &self.max_sum
    }
}

#[cfg(test)]
mod tests {
    use rand::{prelude::SliceRandom, thread_rng};

    use crate::{nodes::Node, utils::MaxSubArraySum};

    #[test]
    fn max_sub_array_sum_works() {
        let mut rng = thread_rng();
        let n = 1000000 / 2;
        let mut nodes: Vec<_> = (-n..=n).collect();
        nodes.shuffle(&mut rng);
        // See https://en.wikipedia.org/wiki/Maximum_subarray_problem#Kadane's_algorithm
        let expected_answer = {
            let mut best_sum = 0;
            let mut current_sum = 0;
            for val in nodes.iter(){
                current_sum = 0.max(current_sum + val);
                best_sum = best_sum.max(current_sum);
            }
            best_sum
        };
        let nodes: Vec<MaxSubArraySum> = nodes
            .into_iter()
            .map(|x| MaxSubArraySum::initialize(&x))
            .collect();
        let result = nodes
            .iter()
            .fold(MaxSubArraySum::initialize(&0), |acc, new| {
                MaxSubArraySum::combine(&acc, new)
            });
        assert_eq!(result.value(), &expected_answer);
    }
}