algorist 0.10.2

Algorithms and data structures for competitive programming
Documentation 
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
73
74

use crate::math::Number;

pub trait MaxSum {
    type Output;

    fn max_sum(&self) -> Self::Output;
}

impl<T: Number + Ord> MaxSum for [T] {
    type Output = T;

    fn max_sum(&self) -> T {
        max_sum(self)
    }
}

/// Returns the maximum sum of a contiguous sub-array within the given array.
/// Implemented using Kadane's algorithm.
pub fn max_sum<T: Number + Ord>(arr: &[T]) -> T {
    let mut max_sum = T::zero();
    let mut current_sum = T::zero();

    for &num in arr {
        current_sum = current_sum.max(T::zero()) + num;
        max_sum = max_sum.max(current_sum);
    }
    max_sum
}

pub fn max_sum_from_iter<T: Number + Ord, I: Iterator<Item = T>>(iter: I) -> T {
    let mut max_sum = T::zero();
    let mut current_sum = T::zero();

    for num in iter {
        current_sum = current_sum.max(T::zero()) + num;
        max_sum = max_sum.max(current_sum);
    }
    max_sum
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_max_sum() {
        assert_eq!(max_sum(&[1, 2, 3, 4, 5]), 15);
        assert_eq!(max_sum(&[1, -2, 3, -4, 5]), 5);
        assert_eq!(max_sum(&[-1, -2, -3, -4, -5]), 0);
        assert_eq!(max_sum(&[1, 2, 3, 4, -1, 5, -1, -2, -3, -4, -5]), 14);
    }

    #[test]
    fn test_max_sum_trait() {
        assert_eq!([1, 2, 3, 4, 5].max_sum(), 15);
        assert_eq!([1, -2, 3, -4, 5].max_sum(), 5);
        assert_eq!([-1, -2, -3, -4, -5].max_sum(), 0);
        assert_eq!([1, 2, 3, 4, -1, 5, -1, -2, -3, -4, -5].max_sum(), 14);

        let arr = [1, 2, 3, 4, 5];
        assert_eq!(arr.max_sum(), 15);
    }

    #[test]
    fn test_max_sum_from_iter() {
        assert_eq!(max_sum_from_iter([1, 2, 3, 4, 5].iter().copied()), 15);
        assert_eq!(max_sum_from_iter([1, -2, 3, -4, 5].iter().copied()), 5);
        assert_eq!(max_sum_from_iter([-1, -2, -3, -4, -5].iter().copied()), 0);
        assert_eq!(
            max_sum_from_iter([1, 2, 3, 4, -1, 5, -1, -2, -3, -4, -5].iter().copied()),
            14
        );
    }
}