aboutsummaryrefslogtreecommitdiff
path: root/buy_sell_stock.rs
diff options
context:
space:
mode:
Diffstat (limited to 'buy_sell_stock.rs')
-rw-r--r--buy_sell_stock.rs33
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));
+}