algorithms_rs/chapter4/
find_maximum_subarray.rs

1use num_traits::bounds::Bounded;
2use num_traits::Zero;
3use std::cmp::PartialOrd;
4use std::fmt::Debug;
5use std::ops::AddAssign;
6
7fn find_max_crossing_subarray<T>(
8    array: &[T],
9    low: usize,
10    mid: usize,
11    high: usize,
12) -> (usize, usize, T)
13where
14    T: Zero + Bounded + AddAssign + PartialOrd + Copy + Debug,
15{
16    let mut left_sum = T::min_value();
17    let mut sum = T::zero();
18    let mut max_left = 0usize;
19    // Note: 一定要这样使用不能写成 mid..=low
20    for i in (low..=mid).rev() {
21        if let Some(v) = array.get(i) {
22            sum = sum + *v;
23            if sum > left_sum {
24                left_sum = sum;
25                max_left = i;
26            }
27        }
28    }
29    let mut right_sum = T::min_value();
30    let mut sum = T::zero();
31    let mut max_right = 0usize;
32    for i in (mid + 1)..=high {
33        if let Some(v) = array.get(i) {
34            sum = sum + *v;
35            if sum > right_sum {
36                right_sum = sum;
37                max_right = i;
38            }
39        }
40    }
41    (max_left, max_right, left_sum + right_sum)
42}
43
44/// find maximum sub array
45pub fn find_maximum_subarray<T>(array: &[T], low: usize, hight: usize) -> (usize, usize, T)
46where
47    T: Zero + Bounded + AddAssign + PartialOrd + Default + Clone + Copy + Debug,
48{
49    if hight == low {
50        let sum = array.get(low).map(|v| v.clone()).unwrap_or_default();
51        return (low, hight, sum);
52    } else {
53        let mid = ((low as f64 + hight as f64) / 2f64).floor() as usize;
54
55        let (left_low, left_heigh, left_sum) = find_maximum_subarray(array, low, mid);
56        let (right_low, right_high, right_sum) = find_maximum_subarray(array, mid + 1, hight);
57        let (cross_low, cross_hight, cross_sum) =
58            find_max_crossing_subarray(array, low, mid, hight);
59
60        if left_sum >= right_sum && left_sum >= cross_sum {
61            return (left_low, left_heigh, left_sum);
62        } else if right_sum >= left_sum && right_sum >= cross_sum {
63            return (right_low, right_high, right_sum);
64        } else {
65            return (cross_low, cross_hight, cross_sum);
66        }
67    }
68}
69
70#[test]
71fn test_find_maximum_subarray() {
72    let array = vec![-2, 1, -3, 4, -1, 2, 1, -5, 4];
73    let result = find_maximum_subarray(&array, 0, array.len() - 1);
74    println!(
75        "start is {}, end is {}, sum is {}",
76        result.0, result.1, result.2
77    );
78}
79
80#[test]
81fn test_array_range() {
82    let array = vec![0, 1, 2];
83    let low = 0;
84    let high = array.len();
85    for idx in low..high {
86        println!("{}", array[idx]);
87    }
88    // 输出 0， 1， 2
89    for idx in (high - 1)..=low {
90        println!("{}", array[idx]);
91    }
92    // 不会输出任何东西
93}
algorithms_rs/chapter4/find_maximum_subarray.rs

algorithms_rs/chapter4/
find_maximum_subarray.rs
