algo 0.1.9

Algorithms & Data Structure implementations
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

use std::ops::Add;

pub fn max_subarray<T>(arr: &[T]) -> (usize, usize, T)
    where T: Copy,
          T: Add<Output = T>,
          T: PartialOrd
{
    let len = arr.len();
    max_subarray_rec(arr, 0, len - 1)
}

fn max_subarray_rec<T>(arr: &[T], low: usize, high: usize) -> (usize, usize, T)
    where T: Copy,
          T: Add<Output = T>,
          T: PartialOrd
{
    if low == high {
        (low, high, arr[low])
    } else {
        let mid = (high + low) / 2;

        let (left_low, left_high, left_max) = max_subarray_rec(arr, low, mid);
        let (right_low, right_high, right_max) = max_subarray_rec(arr, mid + 1, high);
        let (cross_low, cross_high, cross_max) = cross_max_subarray(arr, low, mid, high);

        if left_max >= right_max && left_max >= cross_max {
            (left_low, left_high, left_max)
        } else if right_max >= left_max && right_max >= cross_max {
            (right_low, right_high, right_max)
        } else {
            (cross_low, cross_high, cross_max)
        }
    }
}

fn cross_max_subarray<T>(arr: &[T], low: usize, mid: usize, high: usize) -> (usize, usize, T)
    where T: Copy,
          T: Add<Output = T>,
          T: PartialOrd
{
    let (left_idx, left_max) = cross_part_max(arr, (low...mid).rev());
    let (right_idx, right_max) = cross_part_max(arr, (mid + 1)...high);

    (left_idx, right_idx, left_max + right_max)
}

fn cross_part_max<T, I>(arr: &[T], mut range: I) -> (usize, T)
    where T: Copy,
          T: Add<Output = T>,
          T: PartialOrd,
          I: Sized + Iterator<Item = usize>
{
    let mut idx = range.next().unwrap();
    let mut max = arr[idx];
    let mut sum = max;

    for i in range {
        sum = sum + arr[i];

        if sum > max {
            max = sum;
            idx = i;
        }
    }

    (idx, max)
}

#[test]
fn test_simple() {
    let arr = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7];

    let (low, high, sum) = max_subarray(&arr);

    assert_eq!(low, 7);
    assert_eq!(high, 10);
    assert_eq!(sum, 43);
}

#[bench]
fn bench_simple(b: &mut ::test::Bencher) {
    b.iter(|| {
        let arr = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7];
        max_subarray(&arr);
    })
}