102 lines
2.3 KiB
Rust
102 lines
2.3 KiB
Rust
#[derive(Debug)]
|
|
struct State {
|
|
price: i32,
|
|
profit: i32,
|
|
}
|
|
|
|
impl State {
|
|
fn new() -> State {
|
|
State {
|
|
price: i32::MAX,
|
|
profit: 0,
|
|
}
|
|
}
|
|
|
|
fn update(&self, previous: &State, price: i32) -> State {
|
|
let new_price = std::cmp::min(self.price, price - previous.profit);
|
|
|
|
State {
|
|
price: new_price,
|
|
profit: std::cmp::max(self.profit, price - new_price),
|
|
}
|
|
}
|
|
}
|
|
|
|
impl Solution {
|
|
pub fn max_profit(k: i32, prices: Vec<i32>) -> i32 {
|
|
let mut states: Vec<State> = (0..=k).map(|_| State::new()).collect();
|
|
|
|
prices.iter().for_each(|p| {
|
|
let mut new_states = Vec::from([State::new()]);
|
|
|
|
new_states.extend(
|
|
states
|
|
.iter()
|
|
.zip(states.iter().skip(1))
|
|
.map(|(prev_state, state)| state.update(prev_state, *p)),
|
|
);
|
|
|
|
states = new_states;
|
|
});
|
|
|
|
states.last().expect("No state is present").profit
|
|
}
|
|
}
|
|
struct Solution {}
|
|
|
|
fn main() {
|
|
println!("Hello World!");
|
|
}
|
|
|
|
#[cfg(test)]
|
|
mod tests_max_profit {
|
|
use super::*;
|
|
|
|
#[test]
|
|
fn test_small_example() {
|
|
assert_eq!(Solution::max_profit(2, vec![2, 4, 1]), 2);
|
|
}
|
|
|
|
#[test]
|
|
fn test_bigger_example() {
|
|
assert_eq!(Solution::max_profit(2, vec![3, 2, 6, 5, 0, 3]), 7);
|
|
}
|
|
|
|
#[test]
|
|
fn test_small_no_transaction() {
|
|
assert_eq!(Solution::max_profit(0, vec![2, 4, 1]), 0);
|
|
}
|
|
|
|
#[test]
|
|
fn test_small_one_transaction() {
|
|
assert_eq!(Solution::max_profit(1, vec![2, 4, 1]), 2);
|
|
}
|
|
|
|
#[test]
|
|
fn test_bigger_one_transaction() {
|
|
assert_eq!(Solution::max_profit(1, vec![3, 2, 6, 5, 0, 3]), 4);
|
|
}
|
|
|
|
#[test]
|
|
fn test_big_all_transactions() {
|
|
assert_eq!(
|
|
Solution::max_profit(10, vec![3, 2, 6, 5, 0, 3, 1, 13, 5, 2, 1, 9, 4, 5, 69, 42]),
|
|
92
|
|
);
|
|
}
|
|
|
|
#[test]
|
|
fn test_buy_expensive() {
|
|
assert_eq!(Solution::max_profit(2, vec![2, 3, 14, 15]), 13);
|
|
}
|
|
|
|
#[test]
|
|
fn test_accumulates_profit() {
|
|
assert_eq!(Solution::max_profit(5, vec![1, 2, 1, 2, 1, 2, 1, 2, 5]), 7);
|
|
}
|
|
|
|
#[test]
|
|
fn test_no_profit_made() {
|
|
assert_eq!(Solution::max_profit(2, vec![5, 4]), 0);
|
|
}
|
|
}
|