diff options
Diffstat (limited to 'buy_sell_stock.rs')
-rw-r--r-- | buy_sell_stock.rs | 33 |
1 files changed, 33 insertions, 0 deletions
diff --git a/buy_sell_stock.rs b/buy_sell_stock.rs new file mode 100644 index 0000000..268482f --- /dev/null +++ b/buy_sell_stock.rs @@ -0,0 +1,33 @@ +use std::collections::HashMap; +struct Solution; + +#[derive(PartialEq, Eq, Hash, Copy, Clone)] +enum Invested { + Yes, No, Cooldown +} + +impl Solution { + pub fn max_profit(prices: Vec<i32>) -> i32 { + Self::dp(&prices, 0, Invested::No, &mut HashMap::new()) + } + fn dp(prices: &[i32], day: usize, invested: Invested, memo: &mut HashMap<(usize, Invested), i32>) -> i32 { + if day == prices.len() { + 0 + } else if let Some(profit) = memo.get(&(day, invested)) { + *profit + } else { + let ans = match invested { + Invested::Yes => Self::dp(prices, day + 1, invested, memo).max(prices[day] + Self::dp(prices, day + 1, Invested::Cooldown, memo)), + Invested::No => Self::dp(prices, day + 1, invested, memo).max(-prices[day] + Self::dp(prices, day + 1, Invested::Yes, memo)), + Invested::Cooldown => Self::dp(prices, day + 1, Invested::No, memo) + }; + memo.insert((day, invested), ans); + ans + } + } +} + +fn main() { + let prices = vec![1,2,3,0,2]; + print!("{}", Solution::max_profit(prices)); +} |