pofk_algorithm 0.0.3

A collection of efficient algorithms implemented in Rust for real-world projects.
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

//! House Robber (Generic, Production-Grade)
//!
//! Returns the maximum amount that can be robbed without robbing adjacent houses.
//!
//! # Type Parameters
//! * `T`: Value type. Must implement `Copy` + `Ord` + `Add<Output = T>` + `Default`.
//!
//! # Example
//! ```rust
//! use pofk_algorithm::dp_algorithms::house_robber::*;
//! let nums = vec![1,2,3,1];
//! assert_eq!(house_robber(&nums), 4);
//! ```
use std::ops::Add;

pub fn house_robber<T>(nums: &[T]) -> T
where
    T: Copy + Ord + Add<Output = T> + Default,
{
    let n = nums.len();
    if n == 0 { return T::default(); }
    if n == 1 { return nums[0]; }
    let mut prev1 = T::default();
    let mut prev2 = T::default();
    for &num in nums {
        let temp = prev1;
        prev1 = prev1.max(prev2 + num);
        prev2 = temp;
    }
    prev1
}