maxsubarray.rs

maxsubarray.rs

// Cargo.toml
[package]
name = "maxsubarray"
version = "0.1.0"
edition = "2018"

[dependencies]

[dev-dependencies]
criterion = "0.3.1"
rand = "0.7.3"

[[bench]]
name = "my_benchmark"
harness = false


// benchmarks/my_benchmark.rs
use core::time::Duration;
use criterion::{criterion_group, criterion_main, BenchmarkId, Criterion};
use maxsubarray::Solution;
use rand::distributions::{Distribution, Uniform};

fn rand_vec(n: usize) -> Vec<i32> {
    let between = Uniform::from(-100..100);
    let mut rng = rand::thread_rng();
    between.sample_iter(&mut rng).take(n).collect()
}

fn bench_fibs(c: &mut Criterion) {
    let mut group = c.benchmark_group("MaxSubarray");
    group.warm_up_time(Duration::from_millis(5));
    group.measurement_time(Duration::from_millis(10));
    group.sample_size(10);

    let mut rand_arrays: Vec<Vec<i32>> = Vec::with_capacity(100);
    for i in [
        1, 2, 5, 10, 15, 20, 25, 30, 50, 75, 100, 150, 200, 300, 500, 750, 1000,
    ]
    .iter()
    {
        rand_arrays.push(rand_vec(*i));
    }

    for i in rand_arrays.iter() {
        group.bench_with_input(BenchmarkId::new("N", i.len()), i, |b, i| {
            b.iter(|| Solution::max_sub_array(i.clone()))
        });
        group.bench_with_input(BenchmarkId::new("N**2", i.len()), i, |b, i| {
            b.iter(|| Solution::max_sub_array_n2(i.clone()))
        });
        group.bench_with_input(BenchmarkId::new("N**3", i.len()), i, |b, i| {
            b.iter(|| Solution::max_sub_array_n3(i.clone()))
        });
    }
    group.finish();
}

criterion_group!(benches, bench_fibs);
criterion_main!(benches);


// src/lib.rs
pub struct Solution {}

impl Solution {
    pub fn max_sub_array(nums: Vec<i32>) -> i32 {
        let mut best = i32::MIN;
        let mut sum = 0;
        // O(N)
        for n in nums {
            sum += n;
            if sum > best {
                best = sum;
            }
            if sum < 0 {
                sum = 0
            }
        }

        best
    }

    pub fn max_sub_array_n2(nums: Vec<i32>) -> i32 {
        let mut best = i32::MIN;
        let mut arraysum: Vec<Vec<i32>> = vec![vec![0; nums.len()]; nums.len()];

        // N * N ~ O(N**2)

        // 0 1 2 3
        //   1 3 5
        //     3 6
        //       6

        best = *nums.iter().max().unwrap();
        arraysum[0] = nums.clone();

        for start in 1..nums.len() {
            for row in 1..=start {
                let elem = arraysum[row - 1][start - 1] + nums[start];
                arraysum[row][start] = elem;
                if elem > best {
                    best = elem;
                }
            }
        }
        best
    }

    pub fn max_sub_array_n3(nums: Vec<i32>) -> i32 {
        let mut best = i32::MIN;

        // N elements in nums
        // N * N * N ~ O(N**3)

        for start in 0..nums.len() {
            for end in start..nums.len() {
                let s = nums[start..=end].iter().sum();
                if s > best {
                    best = s
                }
            }
        }
        best
    }
}

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

    #[test]
    fn leetcode_example() {
        assert_eq!(
            Solution::max_sub_array(vec![-2, 1, -3, 4, -1, 2, 1, -5, 4]),
            6
        );
    }

    #[test]
    fn negative_example() {
        assert_eq!(Solution::max_sub_array(vec![-6, -2, -1]), -1);
    }

    #[test]
    fn zero_example() {
        assert_eq!(Solution::max_sub_array(vec![0]), 0);
    }
}