algorithms-rs 0.1.11

Implementation of The Introduction to Algorithms Thrid Edition By Rust programming Language
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

use num_traits::bounds::Bounded;
use num_traits::Zero;
use std::cmp::PartialOrd;
use std::fmt::Debug;
use std::ops::AddAssign;

fn find_max_crossing_subarray<T>(
    array: &[T],
    low: usize,
    mid: usize,
    high: usize,
) -> (usize, usize, T)
where
    T: Zero + Bounded + AddAssign + PartialOrd + Copy + Debug,
{
    let mut left_sum = T::min_value();
    let mut sum = T::zero();
    let mut max_left = 0usize;
    // Note: 一定要这样使用不能写成 mid..=low
    for i in (low..=mid).rev() {
        if let Some(v) = array.get(i) {
            sum = sum + *v;
            if sum > left_sum {
                left_sum = sum;
                max_left = i;
            }
        }
    }
    let mut right_sum = T::min_value();
    let mut sum = T::zero();
    let mut max_right = 0usize;
    for i in (mid + 1)..=high {
        if let Some(v) = array.get(i) {
            sum = sum + *v;
            if sum > right_sum {
                right_sum = sum;
                max_right = i;
            }
        }
    }
    (max_left, max_right, left_sum + right_sum)
}

/// find maximum sub array
pub fn find_maximum_subarray<T>(array: &[T], low: usize, hight: usize) -> (usize, usize, T)
where
    T: Zero + Bounded + AddAssign + PartialOrd + Default + Clone + Copy + Debug,
{
    if hight == low {
        let sum = array.get(low).map(|v| v.clone()).unwrap_or_default();
        return (low, hight, sum);
    } else {
        let mid = ((low as f64 + hight as f64) / 2f64).floor() as usize;

        let (left_low, left_heigh, left_sum) = find_maximum_subarray(array, low, mid);
        let (right_low, right_high, right_sum) = find_maximum_subarray(array, mid + 1, hight);
        let (cross_low, cross_hight, cross_sum) =
            find_max_crossing_subarray(array, low, mid, hight);

        if left_sum >= right_sum && left_sum >= cross_sum {
            return (left_low, left_heigh, left_sum);
        } else if right_sum >= left_sum && right_sum >= cross_sum {
            return (right_low, right_high, right_sum);
        } else {
            return (cross_low, cross_hight, cross_sum);
        }
    }
}

#[test]
fn test_find_maximum_subarray() {
    let array = vec![-2, 1, -3, 4, -1, 2, 1, -5, 4];
    let result = find_maximum_subarray(&array, 0, array.len() - 1);
    println!(
        "start is {}, end is {}, sum is {}",
        result.0, result.1, result.2
    );
}

#[test]
fn test_array_range() {
    let array = vec![0, 1, 2];
    let low = 0;
    let high = array.len();
    for idx in low..high {
        println!("{}", array[idx]);
    }
    // 输出 0， 1， 2
    for idx in (high - 1)..=low {
        println!("{}", array[idx]);
    }
    // 不会输出任何东西
}