algos 0.6.8

A collection of algorithms in Rust
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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

/// Kadane's algorithm to find the maximum subarray sum in a slice of `i32`.
///
/// If the input slice is empty, returns `None`. Otherwise, returns `Some(<max sum>)`.
///
/// # Examples
///
/// ```
/// use algos::cs::dynamic::kadane::kadane;
///
/// let arr = vec![-2, 1, -3, 4, -1, 2, 1, -5, 4];
/// assert_eq!(kadane(&arr), Some(6));  // subarray [4, -1, 2, 1] has sum 6
///
/// let empty: Vec<i32> = vec![];
/// assert_eq!(kadane(&empty), None);
/// ```
pub fn kadane(arr: &[i32]) -> Option<i32> {
    if arr.is_empty() {
        return None;
    }
    let mut current_sum = arr[0];
    let mut max_sum = arr[0];

    for &val in &arr[1..] {
        // Either extend the current subarray or start a new one at `val`
        current_sum = current_sum.max(0) + val;
        max_sum = max_sum.max(current_sum);
    }

    Some(max_sum)
}

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

    #[test]
    fn test_empty_array() {
        let arr: [i32; 0] = [];
        assert_eq!(kadane(&arr), None, "Empty array should return None");
    }

    #[test]
    fn test_single_element() {
        let arr = [42];
        assert_eq!(
            kadane(&arr),
            Some(42),
            "Single-element array should return that element"
        );
    }

    #[test]
    fn test_all_negative() {
        let arr = [-8, -3, -6, -2, -5, -4];
        // Kadane's should pick the largest single negative element: -2
        assert_eq!(kadane(&arr), Some(-2));
    }

    #[test]
    fn test_mixed_values() {
        let arr = [1, -2, 3, 5, -1];
        // The subarray [3, 5] or [3, 5, -1] if we consider the negative is still beneficial or not:
        //   3 + 5 = 8, 3 + 5 + (-1) = 7, so max subarray sum is 8
        assert_eq!(kadane(&arr), Some(8));
    }

    #[test]
    fn test_large_positive() {
        let arr = [2, 2, 2, 2, 2];
        // All positives, so entire array is the max subarray
        assert_eq!(kadane(&arr), Some(10));
    }

    #[test]
    fn test_subarray_in_the_middle() {
        let arr = [-1, -2, 4, 5, -1, -2];
        // Max subarray is [4,5] => sum=9
        assert_eq!(kadane(&arr), Some(9));
    }

    #[test]
    fn test_subarray_at_the_end() {
        let arr = [-5, -1, 2, 3, 7];
        // Max subarray is [2,3,7] => sum=12
        assert_eq!(kadane(&arr), Some(12));
    }

    #[test]
    fn test_large_fluctuations() {
        let arr = [10, -5, 2, -1, 15, -20, 25, -2];
        // A plausible max subarray is [10, -5, 2, -1, 15, -20, 25] or shorter; let's break it down:
        //   partial sums: 10 -> 5 -> 7 -> 6 -> 21 -> 1 -> 26 -> 24
        // The largest encountered is 26
        assert_eq!(kadane(&arr), Some(26));
    }
}